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

#include <bits/stdc++.h>
#define MAX 1000
using namespace std;

int main() {
    int dp[MAX], data[MAX];
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> data[i];
            dp[i] = data[i];
        }

        for (int i = 1; i < n; i++)
            for (int j = i + 1; j <= n; j++) {
                if (data[i] < data[j]) {
                    dp[j] = max(dp[j], dp[i] + data[j]);
                }
            }
        int k = -1;
        for (int i = 1; i <= n; i++) {
            if (dp[i] > k)
                k = dp[i];
        }
        cout << k << endl;
    }
}