Question
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?
Naive solution: O(n^2)
res[i]代表i下标结尾的最长LIS。对于res[i],如果num[i] > num[j] (j < i), res[i] 为满足此条件的res[j] + 1, 每一步取最优。
public class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) {
return 0;
}
int[] res = new int[nums.length+1];
res[0] = 1;
int index = 1;
for(int i = 1; i < nums.length; i++) {
int max = 1;
for(int j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
max = Math.max(max, res[j]+1);
}
}
res[i] = max;
index = Math.max(index, res[i]);
} // for i
return index;
} // lengthOfInt
}
O(nlgn) solution:
对i属于(1, nums.length], tails代表长度为i的LIS最小的末尾。对每个num二分查找更新tails的位置，如果num大于存在于tails的所有末尾值则size++。怎么什么都会🙄
public class Solution {
// tails[] means for each length = i LIS, the min tail of it
// for each num, binary search in tails[]
// if it is larger than tails[end], size++
// else in tails, find the right update place
// O(nlgn)
public int lengthOfLIS(int[] nums) {
int tails[] = new int[nums.length];
int size = 0;
for(int num: nums){
int begin = 0, end = size;
// find m when tail[m-1] < mid < tail[m]
while(begin < end){
int mid = (begin + end)/2;
if(tails[mid] < num){
begin = mid + 1;
}else{
end = mid;
}
}
tails[begin] = num;
if(begin == size) size++;
}
return size;
}
}