题解 | 最大上升子序列和

#include <iostream>

using namespace std;
#define N 1010
int a[N];   // 存储原数据
int f[N];   // f[i] : 以a[i]结尾的最长上升子序列和
int n;

int main()
{
    int res = -1e8;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        scanf("%d",&a[i]);
    }
    for(int i = 1; i <= n; ++i){
        // 遍历1 ~ i-1, 并求出以a[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]);
            }
        }
        res = max(res,f[i]);
    }
    cout << res << endl;

    return 0;
}