最长上升子序列

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;
        }
    }

#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);
}
/*
*/