[674. 最长连续递增序列](https://qiekn.notion.site/674-43d91fc58e0a4fabaedb7875a436689d)

动态规划 $O(n^2)$

April 14, 2024 10:00 PM (GMT+8)

dp[i] 表示 [0, i] 以 nums[i] 结尾的最长递增子序列的长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), res = 0;
        vector<int> f(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }
        return res;
    }
};

贪心 + 二分 $O(nlgn)$

贪心：如果我们要使上升子序列尽可能的长，则要让序列上升得尽可能慢，因此我们希望每次在上升子序列 最后加上的 那个数 尽可能的小。

维护一个 help 数组，使用二分查找 help 中最靠右的 ≥ nums[i] 的数，更新它

<aside> 💡 help 是单调的（反证法很容易证明）

</aside>

class SoluUtion {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> q;
	      // 以每个数结尾的 longest-increasing-subsequence 长度
        for (int x : nums) {
            if (q.empty() || x > q.back()) q.push_back(x);
            else {
                int l = 0, r = q.size() - 1;
                while (l < r) {
                    int mid = (l + r)/ 2;
                    if (q[mid] >= x) r = mid;
                    else l = mid + 1;
                }
                q[l] = x;
            }
        }
        return q.size();
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> q;
	      // 以每个数结尾的 longest-increasing-subsequence 长度
        int idx = 0;
        for (int x : nums) {
            printf("**** Round %d ****\\n", idx);
            if (q.empty() || x > q.back()) q.push_back(x);
            else {
                int l = 0, r = q.size();
                while (l < r) {
                    int mid = (l + r)/ 2;
                    for (int x : q) cout << x << " ", printf("acess mid >> q[%d]\\n", mid);
                    if (q[mid] > x) r = mid;
                    else l = mid + 1;
                }
                for (int x : q) cout << x << " ", printf("acess l >> q[%d]\\n", l);
                if (l < q.size()) q[l] = x;
            }
            printf("**** Round %d pass ****\\n", idx ++);
        }
        return q.size();
    }
};