每日一题：最大和上升子序列

最大和上升子序列 - 题目 - Daimayuan Online Judge

 动态规划，和最长上升子序列类似

状态划分，以第i个数结尾的上升子序列的倒数第二个数可能是第一个数，第二个数，...第i-1个数

从第一个数开始枚举，以它为结尾，首先f[i]=a[i]，自身算一个，然后再根据前一状态推出这一状态，上一个数j一旦确定，就用f[j]+a[i]就行，然后如果a[j]<a[i]，说明可以作为上一个数，然后在众多可行的f[j]+a[i]中取最大值就行

最后遍历一下每个数，比较以每个数为结尾的上升子序列的最大值，输出最大的那个

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int a[N];
int n;
int f[N];
int main()
{
    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[j]<a[i]) f[i] = max(f[i], f[j] + a[i]);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}