Star

Leetcode 300. Longest Increasing Subsequence

Posted on | In |

Question

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?

Solution 1: Dynamic Programming O(n^2)

Explanation:

第一层循环： array中的每一个数
第二层循环： 之前的每个数中，选择比这个数小并且有最长链的那个数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] best = new int[nums.length];
    int max = 1;
    for ( int i=0; i<nums.length; i++) {
        best[i] = 1;
        for ( int j=0; j<i; j++) {
            if (nums[j] < nums[i]) {
                best[i] = Math.max(best[i], best[j] + 1);
            }
        }
        max = Math.max(best[i], max);
    }
    return max;
}

Solution 2: Binary Search O(nlogn)

Explanation:

把之前找到的最长的链存起来。遇到下一个数字，如果比list最后一个数大，就放在list的最后，如果不是，就选择比它大，但是大最少的那个数换掉。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLIS(int[] nums) {
    List<Integer> list = new ArrayList<>();
    for (int n: nums) {
        if (list.size() == 0 || n > list.get(list.size()-1)) {
            list.add(n);
        } else {
            int start = 0;
            int end = list.size();
            while (start < end) {
                int mid = (start+end)/2;
                if (list.get(mid) < n) {
                    start = mid +1 ;
                } else {
                    end = mid;
                }
            }
            list.set(end,n);
        }
    }
    return list.size();
}