Day 49 || 1143.最长公共子序列、1035.不相交的线、 53. 最大子序和 、392.判断子序列
1143.最长公共子序列
题目链接：力扣题目链接
思路：和“718. 最长重复子数组”类似，二维数组，只是增长方式不一样，想通的话就是dp[i-1][j-1]+1，如果不相等就是Math.max(dp[i-1][j],dp[i][j-1])。
1035.不相交的线
题目链接：力扣题目链接
思路：与“1143.最长公共子序列”相同的解题方法。
53. 最大子序和
题目链接：力扣题目链接
思路：dp[i]代表当前值与当前值与dp[i-1]加上当前值中的最大值，维护一个maxValue用来返回最后的最大值结果。
class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length+1];int res = Integer.MIN_VALUE ;for(int i=1;i<=nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1]);res = Math.max(res,dp[i]);}return res;}
}392.判断子序列
题目链接：力扣题目链接
思路：最初的想法是一个类似于双指针和谈心的一个写法while循环最后判断s的指针是否到最后即可。动态规划的方法是二维数组，相同的话更新dp[i][j] = dp[i-1][j-1]+1，不同的话dp[i][j] = dp[i][j-1]，这个和最大公共子序列还是有区别的，因为这个s的字符串不能增删。
时间：2h