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：
這個(gè)問題一開始可以被分解為recursive的子問題，一步一步優(yōu)化就可以得到帶有memorization的iterative解法佣渴。初始化dp[i] = 1港粱，即一個(gè)元素的遞增序列回窘。 假設(shè)以i - 1結(jié)尾的subarray里的LIS為dp[i - 1]谤草，那么我們要求以i結(jié)尾的subarray里的LIS碘举，dp[i]的時(shí)候熙侍，要把這個(gè)新的元素和之前所有的元素進(jìn)行比較啸罢，同時(shí)逐步比較dp[j] + 1與dp[i]，假如發(fā)現(xiàn)更長的序列腐宋，我們則更新dp[i] = dp[j] + 1(找到一個(gè)最大的dp[j])紊服，繼續(xù)增加j進(jìn)行比較。當(dāng)i之前的元素全部便利完畢以后胸竞，我們得到了當(dāng)前以i結(jié)尾的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循環(huán)到length,在minLast中存儲(chǔ)一個(gè)nums中一個(gè)遞減的subarray中的最小值（存儲(chǔ)在minLast中), minLast中尋找時(shí)利用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;
}
}
二刷
方法：構(gòu)造一個(gè)長度為len的數(shù)組tail卫枝，數(shù)組的index表示increasing sub-array的長度煎饼，tail[index]表示長度為index的sub-array中，tail最小的一個(gè)校赤。比如index=2, 有[4,5],[5,6]則tail[index] = 5.
對于后來的數(shù)字x吆玖，我們找到一個(gè)index最大，但是num[index]<x马篮， 然后update這個(gè)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;
}
}
三刷
利用函數(shù)：Arrays.binarySearch(int[] nums, int start, int end, int num)
如果返回值為負(fù)數(shù)，表示沒有找到浑测，然后返回需要插入的位置翅阵，然后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;
}
