300 Longest Increasing Subsequence
1. 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 is4
. 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(nlogn) time complexity?
2. Implementation
(1) DP
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] LIS = new int[n];
Arrays.fill(LIS, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && (LIS[j] + 1 > LIS[i])) {
LIS[i] = LIS[j] + 1;
}
}
}
int res = 0;
for (int e : LIS) {
res = Math.max(e, res);
}
return res;
}
}
(2) Binary Search优化
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n)
Last updated
Was this helpful?