最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]

输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

这题有两种解法，用动态规划是 $O(n^2)$ ，用贪心二分是 $O(n log n)$ 。

动态规划：dp[i]表示以索引 i 结尾的最长递增子序列。

C++15 linesExpandCollapse

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(ans, dp[i]);
            }
        }
    }
    return ans;
}

贪心二分：维护一个 tails 数组，tails[i] 表示长度为 i + 1 的递增子序列中，最小可能结尾的元素。核心思想：对于相同长度的递增子序列，结尾数字越小，未来越容易继续接新的数字。

C++13 linesExpandCollapse

int lengthOfLIS(vector<int>& nums) {
    
    vector<int> tails;
    for (int num : nums) {
        // 在 tails 中找第一个 ≥ num 的数
        auto it = lower_bound(tails.begin(), tails.end(), num);
        // 如果 tails 中所有数都比 num 小，就把 num 加到 tails 最后。
        if (it == tails.end()) tails.push_back(num); 
        // 否则，把找到的第一个比 num 小的数换成 num
        else *it = num;
    }
    return tails.size();
}