[Leetcode] Longest Increasing Subsequence

Problem

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?

Analysis

• 遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数
• tail 表示当前valid数组的最后一个数， 
• 对于当前读到的数x
• 如果x>tail，则把x append到数组中
• 如果x<valid数组的第一个数，则将其替换为x
• 否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x
• 返回valid数组中有效的数个数

时间复杂度: O(nlogn)

Code

	public class Solution {
	public int lengthOfLIS(int[] nums) {
	if(nums==null || nums.length==0) return 0;
	int[] valid = new int[nums.length];
	int idx = 1;
	valid[0] = nums[0];
	for(int i=1; i<nums.length; i++){
	//Case 1: larger than the tail, append
	if(nums[i]>valid[idx-1]){
	valid[idx++] = nums[i];
	//Case 2: smaller than head, repace head
	}else if(nums[i]<valid[0]){
	valid[0] = nums[i];
	}
	//Case 3: otherwise, repace the first number that equal or larger than x
	else{
	int replaceidx = findIdx(valid, nums[i], 0, idx);
	valid[replaceidx] = nums[i];
	}
	}
	return idx;
	}
	//binary search to find the idx of the first number that is equal or larger than target
	public int findIdx(int[] valid, int target, int left, int right){
	if(right-left<1) return left;
	int mid = left + (right-left)/2;
	if(valid[mid]<target)
	return findIdx(valid, target, mid+1, right);
	else return findIdx(valid, target, left, mid);
	}
	}

view raw longest-increasing-subsequence.java hosted with ❤ by GitHub

Reference
[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
[2] https://leetcode.com/problems/longest-increasing-subsequence/