1. 最长公共子序列
1143. 最长公共子序列 - 力扣(LeetCode)
最长公共子数组必须连续,所以一旦元素不相等,当前的最长公共长度不能由前面得来,只能为0
而最长公共子序列,可以断开,所以不相等时,它的长度可以从前面的状态获取(取最大)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// dp[i][j]
int l1 = text1.length();
int l2 = text2.length();
// 第一行第一列预留出来,防止 -1 oob
int[][] dp = new int[l1 + 1][l2 + 1];
// 从第二行第二列开始
for(int i = 1; i < l1 + 1; i++){
for(int j = 1; j < l2 + 1; j++){
// 记得序号 -1
if(text1.charAt(i-1) == text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
// 不相等时,去掉一个,看哪边更大
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[l1][l2];
}
}
2. 不相交的线
1035. 不相交的线 - 力扣(LeetCode)
本质就是求最长公共子序列
3. 最大子数组和
53. 最大子数组和 - 力扣(LeetCode)
前一位如果小于0,那加上前一位只会更小,所以不加文章来源:https://www.uudwc.com/A/pjwzr/
class Solution {
public int maxSubArray(int[] nums) {
int l = nums.length;
int[] dp = new int[l]; // dp[i] 0 - i 的最大子数组和
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < l; i++){
// 前一位如果小于0,那加上前一位只会更小,所以不加
dp[i] = Math.max(dp[i-1], 0) + nums[i];
max = Math.max(dp[i], max);
}
return max;
}
}
文章来源地址https://www.uudwc.com/A/pjwzr/