Description
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example
1 | Input: [10,9,2,5,3,7,101,18] |
Note:
- 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?
Solution
Solution 1: DP, $O(n^2)$
1 | class Solution { |
Solution 2: Binary Search + Greedy
Binary Search + Greedy, build one increasing queue
If new num > the last one in the queue, just add it.
If new num <= the last one, find the first num in the queue which <= the new num, replace it.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] incArray = new int[nums.length];
incArray[0] = nums[0];
int last = 0;
for (int i = 1; i < nums.length; i++){
if (nums[i] > incArray[last]){
last++;
incArray[last] = nums[i];
}
else{
int temp = helper(incArray, 0, last, nums[i]);
incArray[temp] = nums[i];
}
}
return last + 1;
}
private int helper(int[] arr, int left, int right, int target){
while(left < right){
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target){
left = mid + 1;
}
else right = mid;
}
return left;
}
}