LeetCode OJ 300 Longest Increasing Subsequence

Posted on   |  

Question

[LeetCode 300] Given an unsorted array of integers, find the length of longest increasing subsequence.

Submission

Similar to [LeetCode 334], solve the question by using dynamic programming, and the algorithm run in $O(n^2)$ time and can be speed up to $O(nlogn)$ by using binary search.

Solve with dynamic programming

The easiest solution which take $O(n^2)$ running time

Java Submission
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
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] length = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            length[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < length.length; i++) {
            if (length[i] > maxLength) {
                maxLength = length[i];
            }
        }
        return maxLength;
    }
}

By using binary search the running time can be reduced to $O(nlogn)$

Java Submission
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
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int maxLength = 0;
        int[] lastIndex = new int[nums.length+1];

        for (int i = 0; i < nums.length; i++) {
            int lo = 1;
            int hi = maxLength;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (nums[lastIndex[mid]] < nums[i]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }

            int newLength = lo;

            lastIndex[newLength] = i;

            if (newLength > maxLength) {
                maxLength = newLength;
            }
        }

        return maxLength;
    }
}

Explanation

Using an addition array lastIndex to store the index of the last elements of possible increasing subsequences in nums, lastIndex[j] representing the index of the smallest elements in nums in the subsequences with length = j. maxLength will be used to mark the maximum length of the increasing subsequence in the current iteration.

nums = {9, 8, 2, 5, 3, 7, 19, 11, 9} and i = 8

When maxLength = 5, this

ilastIndex[i]Representing Sequence
0--
122
242, 3
352, 3, 7
562, 3, 6

For each iteration, we would like to know whether nums[i] will generate a longer/better increasing subsequences. By using binary search, to find the maximum length l of a subsequences where its last number is just smaller than nums[i], and because the last value of the sequence represented by lastIndex[l+1] is less than the nums[i] (i.e nums[lastIndex[l+1]] > nums[i]), thus, it generate a better increasing subsequences with length = l+1, and lastIndex[l+1] will be updated. If l+1 is greater than the current maximun length, it indicates that a longer increasing subsequence can be found.

References

  1. Longest Increasing Subsequence https://en.wikipedia.org/wiki/Longest_increasing_subsequence