题解 | 最大上升子序列和

//初始化dp为每个数本身
#include<iostream>
#include<math.h>
using namespace std;
int nums[1002];
int dp[1002];  //dp[i][j]表示从i
int main(){
    int k;
    cin>>k;
    int maxl=0;
    
    for(int i=1;i<=k;i++){
        cin>>nums[i];
        dp[i]=nums[i];
    }
    // dp[1]=nums[1];
    for(int i=1;i<=k;i++){
        for(int j=1;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=max(nums[i]+dp[j],dp[i]);
            }
        }
    }
    for(int i=1;i<=k;i++){
        maxl=max(maxl,dp[i]);
    }
    cout<<maxl;
    return 0;
}


/*
8
300 207 155 300 299 170 158 65
*/