题解 | 最大上升子序列和

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000;
int dp[MAXN];
int arr[MAXN];
int Function(int n){
    int answer=0;
    for(int i=0;i<n;i++){
        dp[i]=arr[i];
        for(int j=0;j<i;j++){
            if(arr[j] <arr[i]){
                dp[i] =max(dp[j]+arr[i],dp[i]);
            }
        }
        answer =max(answer,dp[i]);
    }
    return answer;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    cout<<Function(n)<<endl;
    return 0;
}