本文主要是介绍最长重复子数组，最大子序和，最长公共子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
三种类似动态规划对比
#include<bits/stdc++.h>
using namespace std;
class Solution{public:int againMax(vector<int>& num1,vector<int>& num2){vector<vector<int> > dp(num1.size()+1,vector<int>(num2.size()+1,0));//二维数组初始化为0 int result=0;//用来放最大值 for(int i=1;i<=num1.size();i++){for(int j=1;j<=num2.size();j++){if(num1[i-1]==num2[j-1]){//每个数组多放一个，第一位为空不动它 dp[i][j]=dp[i-1][j-1]+1;}if(result<dp[i][j]) result=dp[i][j];}}return result;}int maxSum(vector<int>& num){vector<int> dp(num.size());dp[0]=num[0];//初始化第一个dp就是第一个数组的值，result也是 int result=dp[0];for(int i=1;i<num.size();i++){dp[i]=max(dp[i-1]+num[i],num[i]);//状态转移方程，继续加大还是当前这个元素大 if(result<dp[i]) result=dp[i];}return result;}int maxPub(string s1,string s2){vector<vector<int> > dp(s1.size()+1,vector<int>(s2.size()+1,0));//二维数组初始化为0 for(int i=1;i<=s1.size();i++){for(int j=1;j<=s2.size();j++){if(s1[i-1]==s2[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[s1.size()][s2.size()];}
};
int main(){Solution solution;vector<int> num1;vector<int> num2;int n,m;cin>>n>>m;for(int i=0;i<n;i++){int n1;cin>>n1;num1.push_back(n1);}for(int j=0;j<m;j++){int n2;cin>>n2;num2.push_back(n2);}int result1=solution.againMax(num1,num2);int result2=solution.maxSum(num1);cout<<result1<<" "<<result2;string s1,s2;cin>>s1>>s2;cout<<solution.maxPub(s1,s2);
}
欢迎批评指正！
这篇关于最长重复子数组，最大子序和，最长公共子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
