题解 | 最大上升子序列和

#include <iostream>
using namespace std;
const int N = 1010;
int a[N];
int f[N];
int main() {
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        int Max=0;
        for(int i=1;i<=n;i++){
            f[i]=a[i];
            if(f[i]>Max)Max=f[i];
            for(int j=i;j>=1;j--){
                if(a[i]>a[j]){
                    f[i]=max(f[i],f[j]+a[i]);
                    if(f[i]>Max)Max=f[i];
                }
            }
        }
        cout<<Max<<endl;
    }
}
// 64 位输出请用 printf("%lld")