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-最大上升序列

原文：https://www.cnblogs.com/xihale/p/14669438.html