MENU

LeetCode300. Longest Increasing Subsequence(动态规划)

2019 年 04 月 07 日 • 阅读: 2008 • LeetCode阅读设置

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日 星期日
最后编辑于: 2019 年 04 月 09 日