300.最长上升子序列 (Medium)*

题目描述*

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

示例*

输入: [10,9,2,5,3,7,101,18]

输出: 4

说明*

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。

进阶*

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

参考*

动态规划设计：最长递增子序列

代码*

最长递增子序列 Longest Increasing Subsequence 是比较经典的问题，比较容易想到的是动态规划，复杂度 $O(N^2)$ ，比较难想的是二分查找。

动态规划的核心设计思想是数学归纳法。

定义 dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。最后子序列的最大长度应该是 dp 数组中的最大值。

根据 dp[0] ~ d[i - 1] 求 dp[i] 的过程基本就是找到 nums[j] < nums[i]，dp[i] = max(dp[i], dp[j] + 1)。由此可写出动态规划代码。

二分查找的方法很难想到，参考文章中以 patience game 举例，不太想知道具体证明了，只要写出处理扑克牌的过程就行了。

dp二分查找

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0) {
            return 0;
        }
        vector<int> top;
        int res = 0;
        for(int i = 0; i < nums.size(); i++) {
            int poker = nums[i];
            int l = 0, r = res;
            // 寻找左边界
            while(l < r) {
                int mid = l + (r - l) / 2;
                if(top[mid] > poker) {
                    r = mid;
                }else if(top[mid] < poker) {
                    l = mid + 1;
                }else {
                    r = mid;
                }
            }
            if(l == res) {
                res++;
                top.push_back(poker);
            }else {
                top[l] = poker;
            }
        }
        return res;
    }
};

最后更新: July 23, 2022