3052: 最大上升子序列和

解题思路:经典DP， f[i] 以i节点为结尾的最大上升子序列和

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
const int N = 1e3 + 10;
int a[N],f[N];
using namespace std;
int main()
{
	int n ;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1;  i <= n; i ++){
		f[i] = a[i];
		for(int j = 1; j < i ; j ++){
			if(a[i] > a[j]){
				f[i] = max(f[i], f[j] + a[i]);
			}
		}
	}
	int res = 0;
	for(int i = 1; i <= n; i ++) if(res < f[i]) res = f[i];
	cout << res;
	return 0;
}