最长上升子序列

O(n²)

设a[i]表示以元素re[i]结尾的最长上升子序列长度，初始都为1，最外层循环i，内层找[1,i-1]中re[j] < re[i] 且

a[j] + 1 > a[i] 的来更新a[i]

for(rint i = 1;i <= n; ++i) {
		for(rint j = i - 1; j; --j) {
			if(re[i] > re[j] && a[i] < a[j] + 1) a[i] = a[j] + 1;
		}
	}

O(nlogn)

定义dp[i]表示长度为i的子序列的最小末元素，并由定义可得性质：dp[i]中元素单调递增

开始时len = 1，dp[len] = re[1],循环re[i],re[i] > dp[len] ，则 dp[++len] = re[i];

否则。我们要在dp[]的[1,len-1]中找一个j满足dp[j-1] < re[i] < dp[j],根据“最长上升”我们要dp[j] = re[i];

最终答案为len

由dp的单调性我们可以使用二分，若使用STL注意严格上升是lower_bound(),而不下降是upper_bound();

    dp[1] = re[1];len = 1;
    for(rint i = 2;i <= n + n; ++i) {
        if(re[i] > dp[len]) dp[++len] = re[i];
	else {
	        int j = lower_bound(dp + 1,dp + len + 1,re[i]) - dp;
	        dp[j] = re[i];
	}
}

练习：求序列中某个点开头的最长上升与下降序列的和；

由于我们正反求某个点的严格单调序列答案都是一样的，可以把原序列复制一遍翻转一下接在前面求一下LIS即可

但是非严格则可能存在取重，不能这样做

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
	int f = 1;x = 0;
	char c = getchar();
	for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
	for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	x *= f;
}
template <typename xxx> inline void print(xxx x)
{
	if(x < 0) {
		putchar('-');
		x = -x;
	}
	if(x > 9) print(x/10);
	putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 200100;
const int mod = 1e9+7;
int re[maxn];
int dp[maxn];
int len;
int n;
int main()
{
	read(n);
	for(rint i = 1; i <= n; ++i) {
		read(re[i]); 
		re[i + n] = re[i];
	}
	reverse(re + 1,re + n + 1);
	dp[1] = re[1];len = 1;
	for(rint i = 2;i <= n + n; ++i) {
		if(re[i] > dp[len]) dp[++len] = re[i];
		else {
			int j = lower_bound(dp + 1,dp + len + 1,re[i]) - dp;
			dp[j] = re[i];
		}
	} 
	print(len);
}
/*
*/

最长上升子序列

O(n2)

O(nlogn)

O(n²)