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
原文地址：https://blog.csdn.net/qq_43408590/article/details/143507899
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！