洛谷 AT2827 LIS

题目传送门

解题思路:

用f[i]表示长度为i的最长上升子序列的最小的末尾.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int n,a[100001],f[100001],len = 1;
 8 
 9 int main() {
10     scanf("%d",&n);
11     for(int i = 1;i <= n; i++)
12         scanf("%d",&a[i]);
13     f[1] = a[1];
14     for(int i = 1;i <= n; i++)
15         if(a[i] > f[len])
16             f[++len] = a[i];
17         else {
18             int u = lower_bound(f+1,f+len+1,a[i]) - f;
19             f[u] = a[i];
20         }
21     printf("%d",len);
22     return 0;
23 }