https://leetcode.cn/problems/longest-increasing-subsequence/
思考如果以dp[i]表示i位置的字符的最长递增子序列长度,那么很难找到dp[i]和dp[i-1]的关系,因为dp[i]没有携带是否取当前位置字符的信息。
那么我们以dp[i]表示以位置i结尾的字符的最长递增子序列长度,那么就可以找到dp[i]和dp[i-1]、dp[i-2] …的关系,只要nums[j] < nums[i],则j 和 i就能组成递增子序列 ,我们从i-1比较到0,取dp[j]最大值+1作为dp[i]的值即可。
class Solution {
int result = 0;
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return result;
}
// 表示以指定位置结尾的最长递增子序列
int[] dp = new int[nums.length];
for (int i = 0; i < dp.length; i++) {
dp[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
result = Math.max(result, dp[i]);
}
return result;
}
}
O(N^2)
O(N)
class Solution {
public int lengthOfLIS(int[] nums) {
List<Integer> resultList = new ArrayList<>();
resultList.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
int lastIndex = resultList.size() - 1;
if (nums[i] < resultList.get(lastIndex)) {
// 比当前子序列尾元素还小,需要替换放入合适位置
// 规则是替换掉resultList中最小的比当前元素nums[i]大的元素
int m = 0, n = lastIndex;
while (m < n) {
int mid = (m + n) / 2;
if (resultList.get(mid) < nums[i]) {
m = mid + 1;
} else if (resultList.get(mid) > nums[i]) {
n = mid - 1;
} else {
m = mid;
break;
}
}
if (nums[i] <= resultList.get(m)) {
resultList.set(m, nums[i]);
} else {
resultList.set(m + 1, nums[i]);
}
} else if (nums[i] > resultList.get(lastIndex)) {
// 直接加入上升序列
resultList.add(nums[i]);
}
}
return resultList.size();
}
}
O(NlogN)
O(K) K为最长子序列长度
每个节点计算时,要么就在满足要求时将下一个节点加入当前序列;要么就舍弃当前节点,让前序节点和下一个节点继续判断是否可组成递增序列。这就是分支,所以可考虑使用DFS,并且将结果缓存增加效率。
class Solution {
public int lengthOfLIS(int[] nums) {
int[][] cache = new int[nums.length+1][nums.length];
for(int[] arr : cache) {
Arrays.fill(arr,-1);
}
return dfs(nums, -1, 0, cache);
}
private int dfs(int[] nums, int pre, int cur, int[][] cache) {
if (cur == nums.length) {
return 0;
}
if (cache[pre + 1][cur] > -1) {
return cache[pre + 1][cur];
}
int select = 0;
if (pre < 0 || nums[pre] < nums[cur]) {
// 当前节点加入前节点的序列
select = dfs(nums, cur, cur + 1, cache) + 1;
}
// 不选择当前节点,即跳过本节点
int notSelect = dfs(nums, pre, cur + 1, cache);
// 记忆结果
cache[pre + 1][cur] = Math.max(select, notSelect);
return cache[pre + 1][cur];
}
}