算法 - 最长上升子序列 II

2020-08-05 10:11:32

来源： https://www.acwing.com/problem/content/description/898/

描述：

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

个人觉得思路不算是动态规划，应该算是贪心：

  • 如果w[i] > f[cnt] 的，那么直接加入到后面去。
  • 如果w[i] <= f[cnt]， 那么找到一个大于w[i]的数，然后替换掉。(这里的查找使用二分法)。

所以时间复杂度就是 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int f[N], w[N];

int n, cnt;

int main(){
    cin >> n;
    for( int i = 0; i < n; i++) scanf("%d", &w[i]);

    f[++cnt] = w[0];
    for(int i = 0; i < n; i++) {
        if (w[i] > f[cnt]) f[++cnt] = w[i];
        else {
            int l = 1, r = cnt;
            while (l < r) {
                int mid  = l + r >> 1;
                if (f[mid] >= w[i]) r  = mid;
                else l = mid + 1;
            }
            f[l] = w[i];
        }
    }

    cout << cnt << endl;
    return 0;
}