AcWing 896.最长上升子序列Ⅱ

题目链接：http://www.acwing.com/problem/content/898/

不像是dp，更像是贪心

相对于数据小的上升子序列问题，此题用过的二分后的时间复杂度为 nlog_n。

在本题中首先需要明白：不同长度的上升子序列的最后一个数一定是单调递增的。

所以我们只需要找到一个最大的且小于 a_i 的数，看 a_i 能接到哪个数的后面。

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 int n;
 5 int a[N], q[N];
 6 
 7 int main()
 8 {
 9     cin >> n;
10     for(int i = 0; i < n; i ++)
11         cin >> a[i];
12 
13     int len = 0;
14     q[0] = -2e9;
15     for(int i = 0; i < n; i ++)
16     {
17         int l = 0, r = len;
18         while(l < r)
19         {
20             int mid = l + r + 1 >> 1;
21             if(q[mid] < a[i])  l = mid;
22             else  r = mid - 1;
23         }
24         len = max(len,r + 1);
25         q[r + 1] = a[i];
26     }
27 
28     cout << len;
29 
30     return 0;
31 }