代码随想录算法训练营第五十六天|1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

1143. 最长公共子序列

int longestCommonSubsequence(char * text1, char * text2){int len1 = strlen(text1);int len2 = strlen(text2);int dp[len1+1][len2+1];for (int i = 0; i <= len1; i++){for (int j = 0; j <= len2; j++){dp[i][j] = 0;}}for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++){if (text1[i-1] == text2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);}}}   return dp[len1][len2];
}

1035. 不相交的线

与1143.最长公共子序列一样

int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size){int len1 = nums1Size;int len2 = nums2Size;int dp[len1+1][len2+1];for (int i = 0; i <= len1; i++){for (int j = 0; j <= len2; j++){dp[i][j] = 0;}}for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++){if (nums1[i-1] == nums2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);}}}   return dp[len1][len2];
}

53. 最大子数组和

贪心算法：

int maxSubArray(int* nums, int numsSize){int result = INT_MIN;int count = 0;for (int i=0; i<numsSize; i++){count += nums[i];if (count > result) result = count;if (count < 0) count = 0;}return result;
}

动态规划：

int maxSubArray(int* nums, int numsSize){int dp[numsSize];for (int i = 0; i < numsSize; i++){dp[i] = 0;}dp[0] = nums[0];int ans = nums[0];for (int j = 1; j < numsSize; j++){// 比较的是当前数字大小和上次累加本次的大小dp[j] = fmax(nums[j], dp[j-1] + nums[j]);ans = fmax(dp[j], ans);}return ans;
}

整理一下

int maxSubArray(int* nums, int numsSize){int dp[numsSize];int ans = dp[0] = nums[0];for (int j = 1; j < numsSize; j++){// 比较的是当前数字大小和上次累加本次的大小dp[j] = fmax(nums[j], dp[j-1] + nums[j]);if (dp[j] > ans) ans = dp[j];}return ans;
}