解题思路

传统的动态规划思想是，维护一个dp数组，dp[k] 表示以元素 arr[k] 为末尾的最长严格上升子序列的长度。

但是这个方法要遍历 k 以前的所有位置，找到满足arr[i] < arr[k]且dp[i]最大的那一个，令dp[k] = dp[i] + 1。

时间复杂度为O(n²），这个时间复杂度说实话真的不那么令人满意，有没有更优秀的解法呢？

答案是有的。

根据贪心的思想，如果我维护的子序列上升的速度越慢，那么它就可以加入更多的元素。

比如原始序列 { 1, 4, 6, 2, 3, 5, 8, 7 }，其中子序列 {1, 4, 6 } 比 { 1, 2, 3 } 上升的更快，这两种情况下我们选择 { 1, 2, 3 } 来让后面上升的空间更大。

这样一来，问题就转化成了如何去找到这样一个上升最慢的序列~

具体做法是这样子的：

创建一个动态数组，命名为p。然后遍历arr的每一个元素。对于arr[i]，若该它比p的最后一个元素还大，就将它添加到p的末尾；否则找到p中第一个大于等于它的元素，用arr[i]替换掉这个元素。

当arr遍历完后，数组p的长度就是答案。

单纯的文字可能不容易理解，下面用一个例子具体说明。arr数组为： { 1, 4, 6, 2, 3, 5, 8, 7 }

1、初始p = { }

2、arr[0] = 1，于是p = { 1 }。

3、arr[1] = 4，于是p = { 1, 4 }。

4、arr[2] = 6，于是p = { 1, 4, 6 }。

5、arr[3] = 2，用2替换4，于是p = { 1, 2, 6 }。

6、arr[4] = 3，用3替换6，于是p = { 1, 2, 3 }。

7、arr[5] = 5，于是p = { 1, 2, 3, 5 }。

8、arr[6] = 8，于是p = { 1, 2, 3, 5, 8 }。

9、arr[7] = 7，用7替换8，于是p = { 1, 2, 3, 5, 7 }。

最终答案为p的长度5。

由于p是严格上升的，因此查找p中第一个大于等于arr[i]的元素，可以使用二分查找，时间复杂度为O(log n)。

这样一来整体的时间复杂度就是O(n log n)，比O(n²）要优秀得多。

下面贴出代码。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int &i : arr) {
        cin >> i;
    }
    vector<int> p;
    p.push_back(arr[0]);
    for(int i = 1; i < n; ++i) {
        if(arr[i] > p.back()) {
            p.push_back(arr[i]);
        } else {
            auto pos = lower_bound(p.begin(), p.end(), arr[i]) - p.begin();
            p[pos] = arr[i];
        }
    }
    cout << p.size();
}