zkkKillua's Blog
0%

300.Longest Increasing Subsequence

发表于 更新于 分类于

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(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

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

框架

1
2
3
4
5
6
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {

    }
};

1. 朴素dpO(n^2)

设dp[i]为以a[i]为结尾的最长上升子序列的长度。
dp[i]=max(dp[j]) + 1, j<i且a[j]到a[i]满足递增条件，需要遍历之前所有的dp[j]。

2. dp+二分查找O(nlogn)

设dp[i]为长度为i的上升子序列的最小的末尾元素（即最小的最大值），如1,2,4和1,2,3，dp[3]=3。
遍历序列a，对于每个元素a[i]，有：

  • a[i]>dp[last]
    dp[++last]=a[i]
  • a[i]<dp[last]
    dp[1]~dp[last]之间总能找到一个位置loc，使得dp[loc-1]<a[i]<dp[loc]，那么可以用a[i]替换dp[loc]，代表可以用更小的结尾元素获得同样的长度。
    在方法1中，查找是O(n)的，所以结果是O(n^2)。
    此处，由于dp序列必是非递减的，可以利用二分查找，从而达到O(nlogn)的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int *dp = new int[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = 0;
        
        int resLen = 0;
        for (int i = 0; i < n; i++) {
            if (resLen == 0 || nums[i] > dp[resLen])
                dp[++resLen] = nums[i];
            else {
                int left = 1, right = resLen, mid = (left + right) / 2;
                while (left < right) {
                    if (dp[mid] >= nums[i])
                        right = mid;
                    else
                        left = mid + 1;
                    mid = (left + right) / 2;
                }
                dp[mid] = nums[i];
            }
        }

        delete []dp;
        return resLen;
    }
};