300. Longest Increasing Subsequence (Medium)
https://leetcode.com/problems/longest-increasing-subsequence/
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input:[10,9,2,5,3,7,101,18]
Output: 4 Explanation: The longest increasing subsequence is[2,3,7,101]
, therefore the length is4
.
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(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Solutions
1.
class Solution {
// This solution is a much easier one to understand. The key idea is to make use of dynamic programming.
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int[] track = new int[len + 1];
Arrays.fill(track, 1);
for (int i = len - 1; i >= 0; i--) {
// for ith element, pick the proper subsequent element from (i+1)th to (len-1)th
for (int j = i + 1; j < len; j++) {
// see if meet the condition that requires increasing order
if (nums[i] >= nums[j]) {
continue;
}
track[i] = Math.max(track[i], track[j] + 1);
}
}
int max = 0;
for (int i = 0; i < len; i++) {
max = Math.max(max, track[i]);
}
return max;
}
}
2.
class Solution {
// This solution is a little bit tedious and trivial. It's strongly advised to adopt the
// Solution instead of this one.
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int[] track = new int[len+1];
Arrays.fill(track, 0);
recurse(nums, 0, track);
int max = 0;
for (int i = 0; i < len; i++) {
max = Math.max(max, track[i]);
}
return max;
}
private int recurse(int[] nums, int depth, int[] track) {
int len = nums.length;
if (depth >= len) {
return 0;
}
if (track[depth] > 0) {
return track[depth];
}
int max = 1;
for (int i = depth + 1; i < len; i++) {
int rst = recurse(nums, i, track);
// Do not place following condition statements in front of recurse. Otherwise
// it only search for best subset that contains nums[0]
if (nums[depth] >= nums[i]) {
continue;
}
max = Math.max(max, rst + 1);
}
track[depth] = max;
return max;
}
}