acwing1016. 最大上升子序列和

题目

思路

在求最长子序列个数时，f[i]表示第i个数最长子序列的个数，这里可以将f[i]表示为第i个数时最长子序列的和.

#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N];

int main(){
    int n;
    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[j]<a[i]){
                f[i]=max(f[i],f[j]+a[i]);
            }
        }
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    
    return 0;
}