思路:今天兩題都挺簡(jiǎn)單的，思路就放在一起說了，不相交的線剛剛看題目會(huì)覺得挺麻煩的棚贾，沒有什么思路狞洋，但是多手寫幾道例題弯淘，就會(huì)發(fā)現(xiàn)要實(shí)現(xiàn)不相交的線就是要找出兩個(gè)數(shù)組中可非連續(xù)的相同子數(shù)組，不相交就是要求子數(shù)組不能順序必須保持相對(duì)一致吉懊，這樣題目就轉(zhuǎn)換為了昨天的那題 直接用相同的代碼就可以ac
第二題子數(shù)組和庐橙，一看題意就是很明顯的動(dòng)態(tài)規(guī)劃題假勿，用一維dp數(shù)組解決，dp[i]表示以nums[i]結(jié)尾的最大子序列和态鳖，所以dp[i]要么從dp[i-1]+nums[i]得到转培，要么直接從當(dāng)前開始計(jì)算即nums[i] ，所以遞推公式就是兩者取最大的即可
//題目1035
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
// 也就是求非連續(xù)的最長(zhǎng)公共子序列
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 1; i < nums1.length + 1;i++){
for (int j = 1; j < nums2.length + 1;j++){
if (nums1[i-1] == nums2[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[nums1.length][nums2.length];
}
}
//題目53
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length ; i++) {
// dp[i]表示以nums[i]結(jié)尾的最大子序列和
dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
// 最后一位結(jié)尾不一定最大 所以用res記錄
res = Math.max(res,dp[i]);
}
return res;
}
}
