300.最长递增子序列

问题描述

300.最长递增子序列 本题简写为LIS问题，与LCS问题（最长公共子序列）相对。

解题思路

动态规划

关键在于，dp[i]表示什么含义便于解这道题，子序列不一定连续，所以为了便于求解，dp[i]应该表示为以nums[i - 1]结尾的最长严格递增子序列的长度；

递推关系为:

if (nums[i - 1] > nums[j - 1]) // j < i，表示nums[i - 1]前的任意一个元素
    dp[i] = max(dp[j] + 1, dp[i])

贪心

动态规划的时间复杂度为$O(n^2)$，这里存在一个时间复杂度更低的贪心解法：

动态规划的时间$O(n^2)$的时间复杂度中，$O(n)$的时间复杂度在与遍历整个数组，这是无法避免的；剩下的$O(n)$的时间复杂度，实际上在找一个满足j < i以及nums[j] < nums[i]的并且使dp[j]最大的j；

那么，可以转化为找dp[j]固定的情况下，最小的一个nums[j]，这样必然能够优先满足，nums[i] > nums[j]；因此我们构造一个贪心数组：min_len，min_len[i] = x表示长度为i的上升子序列的最小结尾元素为x。考虑到min_len一定是个单调递增的数组（易证），那么我们可以基于这个单调递增的特性，利用二分查找，找到满足min_len[j] < nums[i]的最大的j，即利用$O(\log n)$找到最佳转移位置。

代码

动态规划

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 1); // dp[0]不考虑，至少有一个元素，所以初始化为1
        // dp[1] = 1;
        // int index = 0;
        int m = 0;
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            if (dp[i] > m)
                m = dp[i];
        }
        return m;
    }
};

贪心+二分

class Solution {
public:
    int GetIdx(vector<int> &min_len_tail, int len, int target) {
        int left = 1, right = len;
        int mid = left + (right - left) / 2;
        while (left < right) {
            if (min_len_tail[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
            mid = left + (right - left) / 2;
        }
        return left;
    }
    int lengthOfLIS(vector<int>& nums) {
        // 贪心，要让序列上升得尽可能慢
        // 先找到第一个波谷
        int n = nums.size();
        vector<int> min_len_tail(n + 1, nums[0]); //min_len_tail[i]表示长度为i的上升子序列的末尾元素的最小值
        int len = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > min_len_tail[len]) {
                min_len_tail[++len] = nums[i];
            } else {
                int idx = GetIdx(min_len_tail, len, nums[i]);
                min_len_tail[idx] = nums[i];
            }
        }
        return len;
    }
};