最长重复子数组，最大子序和，最长公共子序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了最长重复子数组，最大子序和，最长公共子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

三种类似动态规划对比

#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);
}

欢迎批评指正！文章来源地址https://www.toymoban.com/news/detail-850244.html

到了这里，关于最长重复子数组，最大子序和，最长公共子序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！