DP-最大上升序列

本文主要是介绍DP-最大上升序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

进入题目

思路(代码主体)

sum[i]=max(sum[i],sum[j]+m[i])

代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
	int n,Max=0;
	cin>>n;
	vector<int>m(n+1),sum(n+1); //定义两个容器,一个用来存序列,一个存序列大小 
	for(int i=0;i<n;i++)
		cin>>m[i]; //输入序列 
	for(int i=n-1;i>=0;i--)
	{
		sum[i]=m[i]; //初始化序列大小为自己本身 
		for(int j=i+1;j<n;j++)
		{
			if(sum[j]+m[i]>sum[i]&&m[i]<m[j]) //判断(j序列和)是否比(i序列和)大并且是不下降的序列 
				sum[i]=sum[j]+m[i];
		}
		if(sum[i]>sum[Max])Max=i;//找最大值的下标 
	}
	cout<<sum[Max];//输出 
	return 0;
}

这篇关于DP-最大上升序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！