300. Longest Increasing Subsequence

发表于 | 分类于

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

解法1：O(N^2)

经典dp,　dp[i]是到第ｉ个数字的最大递增subsequence, 那么dp[i] = Max(dp[k1], dp[k2], dp[k3]…) + 1, nums[i] > nums[kn]

C+,

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

解法2：O(NlogN)

解释参考leetcode 的答案解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
In this approach, we scan the array from left to right. We also make use of a dpdpdp array initialized with all 0's. This dpdpdp array is meant to store the increasing subsequence formed by including the currently encountered element. While traversing the numsnumsnums array, we keep on filling the dpdpdp array with the elements encountered so far. For the element corresponding to the jthj^{th}j​th​​ index (nums[j]nums[j]nums[j]), we determine its correct position in the dpdpdp array(say ithi^{th}i​th​​ index) by making use of Binary Search(which can be used since the dpdpdp array is storing increasing subsequence) and also insert it at the correct position. An important point to be noted is that for Binary Search, we consider only that portion of the dpdpdp array in which we have made the updations by inserting some elements at their correct positions(which remains always sorted). Thus, only the elements upto the ithi^{th}i​th​​ index in the dpdpdp array can determine the position of the current element in it. Since, the element enters its correct position(iii) in an ascending order in the dpdpdp array, the subsequence formed so far in it is surely an increasing subsequence. Whenever this position index iii becomes equal to the length of the LIS formed so far(lenlenlen), it means, we need to update the lenlenlen as len=len+1len = len + 1len=len+1.
Note: dpdpdp array does not result in longest increasing subsequence, but length of dpdpdp array will give you length of LIS.
Consider the example:
input: [0, 8, 4, 12, 2]
dp: [0]
dp: [0, 8]
dp: [0, 4]
dp: [0, 4, 12]
dp: [0 , 2, 12] which is not the longest increasing subsequence, but length of dpdpdp array results in length of Longest Increasing Subsequence.

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}