本文主要是介绍代码随想录算法训练营第36期DAY57,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
DAY57
今天的好消息:能去华五。
1143最长公共子序列
Code:
- class Solution {
- public:
- int longestCommonSubsequence(string text1, string text2) {
- vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
- for(int i=1;i<=text1.size();i++){
- for(int j=1;j<=text2.size();j++){
- if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
- else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
- }
- }
- return dp[text1.size()][text2.size()];
- }
- };
1035不相交的线
分析法和上一题的图片一样。
- class Solution {
- public:
- int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
- vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
- for(int i=1;i<=nums1.size();i++){
- for(int j=1;j<=nums2.size();j++){
- if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
- else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
- }
- }
- return dp[nums1.size()][nums2.size()];
- }
- };
53最大子序和
竟然做过这一题,
Try again:
想起来了,是贪心算法,sum<0会减小后一位数字,因此continue;同时记录过程中的maxres.
没白学,做出来了,能感觉自己进步了很多:
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- int res=INT_MIN;
- int sum=0;
- for(int i=0;i<nums.size();i++){
- sum+=nums[i];
- res=max(sum,res);
- if(sum<0){
- sum=0;
- continue;
- }
- }
- return res;
- }
- };
动态规划:
动态规划也想出来了,很厉害:
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- int res=0;
- vector<int> dp(nums.size()+1,0);
- for(int i=1;i<=nums.size();i++){
- dp[i]=max(0,dp[i-1]+nums[i-1]);
- res=max(res,dp[i]);
- }
- sort(nums.begin(),nums.end());
- if(nums[nums.size()-1]<0) return nums[nums.size()-1];
- return res;
- }
- };
不用快排可以吗,当然:
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- int res=0,mymax=INT_MIN;
- vector<int> dp(nums.size()+1,0);
- for(int i=1;i<=nums.size();i++){
- mymax=max(mymax,nums[i-1]);
- dp[i]=max(0,dp[i-1]+nums[i-1]);
- res=max(res,dp[i]);
- }
- if(mymax<0) return mymax;
- return res;
- }
- };
看看答案:
题解写得好:实现一下:
记得记录过程中的最大值,并且注意res的初值。
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- vector<int> dp(nums.size());
- int res=nums[0];
- dp[0]=nums[0];
- for(int i=1;i<nums.size();i++) dp[i]=max(dp[i-1]+nums[i],nums[i]),res=max(res,dp[i]);
- return res;
- }
- };
这篇关于代码随想录算法训练营第36期DAY57的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!