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

#include <iostream>
#include <algorithm>

using namespace std;
int main() {
    int n;
    int a[1001], dp[1001];
    while (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        dp[0] = a[0];
        int ans = -1;
        for (int i = 1; i < n; ++i) {
            dp[i] = a[i];
            for (int j = 0; j < i; ++j) {
                if (a[i] > a[j] && dp[j] + a[i] > dp[i]) {
                    dp[i] = dp[j] + a[i];
                }
                ans = max(ans, dp[i]);
            }
        }
        cout << ans << endl;
    }
}