题目简述

给一个序列，求他的最大上升子序列和

思路

和做最长上升子序列一样，只不过状态转移方程变成了：$f[i] = max(f[i],\ f[j] + a[i])$

其他的都一样。

复杂度分析

• 时间复杂度：$O(N ^ 2)$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;
    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]);

        ans = max(ans, f[i]);
    }

    cout << ans << endl;
    return 0;
}