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(n^2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
一刷
题解：
方法1：
这个问题一开始可以被分解为recursive的子问题，一步一步优化就可以得到带有memorization的iterative解法。初始化dp[i] = 1，即一个元素的递增序列。 假设以i - 1结尾的subarray里的LIS为dp[i - 1]，那么我们要求以i结尾的subarray里的LIS，dp[i]的时候，要把这个新的元素和之前所有的元素进行比较，同时逐步比较dp[j] + 1与dp[i]，假如发现更长的序列，我们则更新dp[i] = dp[j] + 1(找到一个最大的dp[j])，继续增加j进行比较。当i之前的元素全部便利完毕以后，我们得到了当前以i结尾的subarray里的LIS，就是dp[i]。
Time Complexity- O(n^2), Space Complexity- O(n^2),
public class Solution {
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int len = nums.length, max = 0;
int[] dp = new int[len];
for(int i=0; i<len; i++){
dp[i] = 1;
for(int j=0; j<i; j++){
if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j]+1);
}
max = Math.max(dp[i], max);
}
return max;
}
}
方法2：
Time Complexity- O(nlogn), Space Complexity- O(n^2),
i从1循环到length,在minLast中存储一个nums中一个递减的subarray中的最小值（存储在minLast中), minLast中寻找时利用binarySearch
public class Solution {
public int lengthOfLIS(int[] nums) {
int[] minLast = new int[nums.length+1];
minLast[0] = Integer.MIN_VALUE;
for(int i=1; i<=nums.length; i++) minLast[i] = Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
// find the first number in minLast >= nums[i]
int index = binarySearch(minLast, nums[i]);
minLast[index] = nums[i];
}
for(int i = nums.length; i >= 1; i--){
if(minLast[i]!= Integer.MAX_VALUE) return i;
}
return 0;
}
// find the first number > num
int binarySearch(int[] minLast, int num){
int start = 0, end = minLast.length - 1;
while(start+1<end){
int mid = (end - start)/2 + start;
if(minLast[mid] < num) start = mid;
else end = mid;
}
return end;
}
}
二刷
方法：构造一个长度为len的数组tail，数组的index表示increasing sub-array的长度，tail[index]表示长度为index的sub-array中，tail最小的一个。比如index=2, 有[4,5],[5,6]则tail[index] = 5.
对于后来的数字x，我们找到一个index最大，但是num[index]<x， 然后update这个tail。如果找到的index刚好等于size, 表示num[index-1]<x, 则num[index] = x
public class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for(int x : nums){
int i = 0, j = size;
while(i!=j){
int m = (i+j)/2;
if(tails[m]<x) i = m+1;
else j = m;
}
tails[i] = x;
if(i == size) size++;
}
return size;
}
}
三刷
利用函数：Arrays.binarySearch(int[] nums, int start, int end, int num)
如果返回值为负数，表示没有找到，然后返回需要插入的位置，然后update
class Solution {
public int lengthOfLIS(int[] nums) {
int[] cache = new int[nums.length];
int size = 0;
for(int num : nums){
int pos = Arrays.binarySearch(cache, 0, size, num);
if(pos<0){
pos = -(pos+1);
}
cache[pos] = num;
if(pos == size) size++;
}
return size;
}
}
如果自己写binarysearch
private int binarySearch(int[] cache, int left, int right, int target){
right--;
while(left<=right){
int mid = left + (right-left)/2;
if(cache[mid] == target) return mid;
else if(cache[mid] < target) left = mid+1;
else right = mid-1;
}
return -left-1;
}
