代码随想录算法训练营第36期DAY57

DAY57

今天的好消息：能去华五。

1143最长公共子序列

Code:

1. class Solution {
2. public:
3.     int longestCommonSubsequence(string text1, string text2) {
4.         vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
5.         for(int i=1;i<=text1.size();i++){
6.             for(int j=1;j<=text2.size();j++){
7.                 if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
8.                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
9.             }
10.         }
11.         return dp[text1.size()][text2.size()];
12.     }
13. };

1035不相交的线

分析法和上一题的图片一样。

1. class Solution {
2. public:
3.     int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
4.         vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
5.         for(int i=1;i<=nums1.size();i++){
6.             for(int j=1;j<=nums2.size();j++){
7.                 if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
8.                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
9.             }
10.         }
11.         return dp[nums1.size()][nums2.size()];
12.     }
13. };

53最大子序和

竟然做过这一题，

Try again:

想起来了，是贪心算法，sum<0会减小后一位数字，因此continue;同时记录过程中的maxres.

没白学，做出来了，能感觉自己进步了很多：

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         int res=INT_MIN;
5.         int sum=0;
6.         for(int i=0;i<nums.size();i++){
7.             sum+=nums[i];
8.             res=max(sum,res);
9.             if(sum<0){
10.                 sum=0;
11.                 continue;
12.             }
13.         }
14.         return res;
15.     }
16. };

动态规划：

动态规划也想出来了，很厉害：

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         int res=0;
5.         vector<int> dp(nums.size()+1,0);
6.         for(int i=1;i<=nums.size();i++){
7.             dp[i]=max(0,dp[i-1]+nums[i-1]);
8.             res=max(res,dp[i]);
9.         }
10.         sort(nums.begin(),nums.end());
11.         if(nums[nums.size()-1]<0) return nums[nums.size()-1];
12.         return res;
13.     }
14. };

不用快排可以吗，当然：

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         int res=0,mymax=INT_MIN;
5.         vector<int> dp(nums.size()+1,0);
6.         for(int i=1;i<=nums.size();i++){
7.             mymax=max(mymax,nums[i-1]);
8.             dp[i]=max(0,dp[i-1]+nums[i-1]);
9.             res=max(res,dp[i]);
10.         }
11.         if(mymax<0) return mymax;
12.         return res;
13.     }
14. };

看看答案：

题解写得好：实现一下：

记得记录过程中的最大值，并且注意res的初值。

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         vector<int> dp(nums.size());
5.         int res=nums[0];
6.         dp[0]=nums[0];
7.         for(int i=1;i<nums.size();i++) dp[i]=max(dp[i-1]+nums[i],nums[i]),res=max(res,dp[i]);
8.         return res;
9.     }
10. };