LeetCode300. Longest Increasing Subsequence（动态规划）

Medium
Accepted：207,426
Submissions：512,883

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in $O(n^2)$ complexity.

Follow up: Could you improve it to $O(nlog n)$ time complexity?

链接

https://leetcode.com/problems/longest-increasing-subsequence

题意

给定一个无序的整数数组，求最长上升子序列（严格上升，大于）的长度。

题解

两种做法，一种是动态规划，时间复杂度$O(n^2)，$一种是“贪心”加二分，时间复杂度$O(nlogn)$。

考虑动态规划，我们可以用dp[i]表示以nums[i]结尾的最长上升子序列长度，初始化为1，容易得到$dp[i] = max \{dp[i], dp[j] + 1 \ if \ nums[i] > nums[j], \ j < i\}$，最后再遍历dp数组得到一个最大的值就试我们要求的答案，注意dp[n-1]并不是最终答案。

考虑“贪心”加二分（传送门）：

新建一个low数组，low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组，对于每一个a[i]，如果a[i] > low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面，即low[++当前最长的LIS长度]=a[i]。
那么，怎么维护low数组呢？
对于每一个a[i]，如果a[i]能接到LIS后面，就接上去；否则，就用a[i]取更新low数组。具体方法是，在low数组中找到第一个大于等于a[i]的元素low[j]，用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话，时间复杂度仍是O(n^2)。我们注意到low数组内部一定是单调不降的，所以我们可以二分low数组，找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn)，所以总的时间复杂度是$O(nlogn)$。

注意，这里得到的low数组并不是实际的最长的上升子序列，但是它的长度我们要求的最后答案。

一个实际的例子可以参考：最长上升子序列nlogn算法。

代码

Runtime: 40 ms, faster than 53.08% of C++ online submissions for Longest Increasing Subsequence.
Memory Usage: 8.7 MB, less than 47.63% of C++ online submissions for Longest Increasing

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

Runtime: 8 ms, faster than 75.08% of C++ online submissions for Longest Increasing Subsequence.
Memory Usage: 8.5 MB, less than 92.37% of C++ online submissions for Longest Increasing Subsequence.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) // 考虑空串
            return 0;
        vector <int> low;
        for (int i = 0; i < n; ++i)
        {
            // low中大于等于nums[i]的第一个位置
            auto it = lower_bound(low.begin(), low.end(), nums[i]);
            if (it == low.end()) // nums[i]大于low中所有元素，直接加上
                low.push_back(nums[i]);
            else // 修改为nums[i]
                *it = nums[i];
        }
        return low.size();
    }
};

参考

The end.
2019年4月7日星期日