题解 | 最大上升子序列和 ,简单动态规划改版

原来的状态转移方程: DP[i]=max(DP[i],DP[j]+1);

新的状态转移方程只是把权重1变成sequences[i]（假设数据输入在sequences[i]中），DP[i]=max(DP[i],DP[j]+sequences[i]);

同时原来DP数组初始化为1即可，现在DP数组初始化为sequences[i]，即：for(int i=0;i<n;i++)DP[i]=sequences[i];

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<int> sequences(n);
        for(int i=0;i<n;i++){
            cin>>sequences[i];
        }
        int res=sequences[0];
        vector<int> DP(n,0);
        for(int i=0;i<n;i++) DP[i]=sequences[i];
        
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(sequences[i]>sequences[j]){
                    DP[i]=max(DP[i],DP[j]+sequences[i]);
                    if(res<DP[i]) res=DP[i];
                }
            }
        }
        cout<<res<<endl;
    }
}
// 64 位输出请用 printf("%lld")