题解 | #最大上升子序列和#

#include <bits/stdc++.h>
#include <climits>
#include <vector>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        vector<int> v;
        int data;
        for (int i = 0; i < n; i++) {
            cin >> data;
            v.push_back(data);
        }
        int dp[n];//dp[i]代表以i结尾的最长递增子序列之和
        int maxv = INT_MIN;
        if (n > 0) maxv = v[0];
        for (int i = 0; i < n; i++) {
            dp[i] = v[i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (v[j] < v[i])
                    dp[i] = max(dp[i], dp[j] + v[i]);
                maxv = max(maxv, dp[i]);
            }
        }
        cout << maxv << endl;
    }
}
// 64 位输出请用 printf("%lld")