[LeetCode] 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?

Thought process:

Dynamic programming:

1. Sub-problem: f[ i ] = the longest increasing subsequence that ends at array[ i ].
2. Function: f[ i ] = max( f[ j ] ) + 1, where array[ j ] < array[ i ]
3. Initialization: if the array has only one number, its LIS is 1. f[ 0 ] = 1.
4. Result: the maximum element of f, because the LIS can end at any number.

Solution 1 (DP):

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 30 31 32 33 34 35

public class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] f = new int[nums.length]; f[0] = 1; for (int i = 1; i < f.length; i++) { int globalLongest = 1; for (int j = i - 1; j >= 0; j--) { if (nums[j] < nums[i]) { int localLongest = f[j] + 1; if (localLongest > globalLongest) { globalLongest = localLongest; } } } f[i] = globalLongest; } int longest = f[0]; for (int i = 1; i < f.length; i++) { if (f[i] > longest) { longest = f[i]; } } return longest; } }

Time complexity: O(n^2).

Follow-up:
As suggested in the problem, the solution can be improved to O(nlogn). This naturally reminds us of binary search. Java's Arrays class provides a binarySearch method, which takes in an array and a key, and returns the index of the key if it's found, or the index where the key should be inserted if it's not found.
The idea is to use this function to generate the LIS. When constructing the LIS, we iterate through the array and search for each element in the current LIS. If the element can be inserted at the end, we can increase the length of our LIS. If not, we replace the current element at that index with our key. This will guarantee we have a smaller number on that index.
In fact, this approach is a greedy algorithm, which will result in an LIS where each element is the smallest possible.

Solution 2 (binary search):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int lengthOfLIS(int[] nums) { int[] lis = new int[nums.length]; int end = 0; for(int num : nums) { int i = Arrays.binarySearch(lis, 0, end, num); if (i < 0) { i = -(i + 1); } lis[i] = num; if (i == end) { end++; } } return end; } }

Time complexity: Binary search takes O(logn). The overall time complexity is O(nlogn).