Longest Increasing Subsequence

LeetCode Q 300 - Longest Increasing Subsequence

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

Solution

Method 1: Dynamic Programming

Time Complexity: O(n^2)

Code:

public int lengthOfLIS(int[] nums) {
	if (nums == null || nums.length == 0) return 0;
	int[] dp = new int[nums.length];
	Arrays.fill(dp, 1); int res = 1;
	for (int i = 1; i < nums.length; i++) {
		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;
}

Method 2: Binary Search

We can find the length as follows:
input array: [10, 9, 2, 5, 3, 7]
helper array (tails): [0, 0, 0, 0, 0, 0]

• tails: [0, 0, 0, 0, 0, 0], len = 0;
• tails: [10, 0, 0, 0, 0, 0], len = 1;
• tails: [9, 0, 0, 0, 0, 0], len = 1;
• tails: [2, 0, 0, 0, 0, 0], len = 1;
• tails: [2, 5, 0, 0, 0, 0], len = 2;
• tails: [2, 3, 0, 0, 0, 0], len = 2;
• tails: [2, 3, 7, 0, 0, 0], len = 3;

Our strategy determined by the following conditions.

• Case 1: If nums[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
• Case 2: If nums[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

Time Complexity: O(nlogn)

Code:

public int lengthOfLIS(int[] nums) {
	if (nums == null || nums.length == 0) return 0;
	int[] tails = new int[nums.length];
	int len = 0;
	for (int num: nums) {
	// use bineary searth to find the largest tail i, that num <= tail[i];
		int i = 0, j = len;
		while (i < j) {
			int mid = i + (j - i) / 2;
			if (tails[mid] < num) 
				i = mid + 1;
			else
				j = mid;
		}
		tails[i] = num; // update the tail 
		if (i == len) len++; // case 1
	}
	return len;
}