300.最大上升子序列

2020-05-17

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 $O(n^2)$ 。

进阶: 你能将算法的时间复杂度降低到 $O(n log n)$ 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

审题

需要注意题目要求的是最长上升子序列，而不是最长上升连续子序列，这一点在示例中得到体现。

测试用例

为了更好地理解题目并考虑到可能的情况，我们写几个有代表性的测试用例：

输入			   输出
[1,2,3,4,5]		5
[5,4,3,2,1]		1
[1,3,2,4,3,5]	4
[99,1,2,3]		3
[1,2,6,3,4,5]	5

第一个是正常的升序数组
第二个是极端情况，没有升序序列
第三个是考虑升序序列不需要连续而给出的 case
第四个是为了考虑到对一个元素计算以其为首的上升子序列长度不一定是最优解
第五个是考虑到简单地维护一个单调栈可能使结果错过最优解

解决

动态规划

如果对每个元素 $i$ ，记以其为结尾的子数组的最长上升序列长度为 $dp(i)$ ，由于我们不要求连续数组，所以需要考虑前面的每一个元素。那么对于前 $i-1$ 个元素为结尾的数组 $dp(j)$ ，第 $i$ 个元素是否能使 $dp(j)$ 的长度增加1，取决于 $i$ 是否大于 $j$ ，因此，有状态转移关系式：

for(int i=1; i<nums.size(); ++i){
    for(int j=0; j<i; ++j){
        if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
    }
}

注意这里有个坑，因为 $dp[i]$ 不一定就是长度为 $i$ 的数组的最大上升子序列长度，只是 $i$ 在序列中的前提下的最大上升子序列长度，因此需要找出 $dp$ 中最大的值。

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

贪心+二分查找

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

因此，维护一个数组 $d[i]$ ，表示长度为 $i$ 的最长上升子序列的末尾元素的最小值，并维护当前最大上升子序列长度 $len$ 。

同时可以使用反证法证明 $d[i]$ 关于 $i$ 单调递增。

遍历 $nums$ ，查找 $d[]$ 找到可以将当前元素插入末尾的数组，当然，我们贪心地希望可以插入当前最长长度的数组。如果不行，就插入到可插入的最长长度数组。值得注意的是，由于 $d[]$ 是单调的，可以使用二分查找，使查找的时间复杂度降为 $O(logN)$ ，总的时间复杂度 $O(NlogN)$ 。

最终， $d[]$ 的长度即为最大上升子序列长度。

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        vector<int> min_tail(n+1, 0);
        min_tail[1] = nums[0];
        int len = 1;
        for(int i=1; i<n; ++i){
            if(nums[i] > min_tail[len]) min_tail[++len] = nums[i];
            else {
                int l = 1;
                int r = len;
                int pos = 0;
                while(l <= r) {
                    int mid = (l + r) >> 1;
                    if(nums[i] > min_tail[mid]) {
                        pos = mid;
                        l = mid + 1; 
                    }
                    else r = mid - 1;
                }
                min_tail[pos + 1] = nums[i];
            }
        }
        return len;
    }
};