300. Longest Increasing Subsequence
Time O(n^2) Space O(n)
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] lengthOfLIS = new int[nums.length];
lengthOfLIS[0] = 1;
int globalMax = lengthOfLIS[0];
for (int i = 1; i < nums.length; i++) {
lengthOfLIS[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (nums[j] < nums[i]) {
lengthOfLIS[i] = Math.max(lengthOfLIS[i], lengthOfLIS[j] + 1);
globalMax = Math.max(globalMax, lengthOfLIS[i]);
}
}
}
return globalMax;
}
}
Time O(n^2) 求解 n 个子问题,每个子问题只被求解一次,子问题最大长度为 n。 Space O(n)
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 0;
int[] visited = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res = Math.max(res, lengthOfLIS(nums, i, visited));
}
return res;
}
private int lengthOfLIS(int[] nums, int pos, int[] visited) {
if (pos == 0) {
return 1;
}
if (visited[pos] > 0) {
return visited[pos];
}
int res = 1;
for (int i = 0; i < pos; i++) {
if (nums[i] < nums[pos]) {
res = Math.max(res, lengthOfLIS(nums, i, visited) + 1);
}
}
visited[pos] = res;
return visited[pos];
}
}
另有 binary search O(nlogn) 解。