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 oobint[][] 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，那加上前一位只会更小，所以不加

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;}
}