1285：最大上升子序列和

  • 最长上升子序列的长度转换为最大上升子序列的和

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 1010;

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

/*
状态表示：f[i] :以a[i]结尾的最大上升子序列

状态转移：
         if(a[j] < a[i])
           f[i] = f[j] + a[i](1<j<i)
初始化：
        f[i] = a[i]

*/ 
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int res = 0;
    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]);
            }
        }
        res = max(res,f[i]);
    }
    cout<<res;    
    return 0;
}