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

#include <iostream>
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int num[n];
        int dp[n];
        for (int i = 0; i < n; i++) {
            cin >> num[i];
            dp[i] = num[i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 注意题中要求为 < ，而不是 <=
                if (num[j] < num[i]) {
                    dp[i] = max(dp[i], num[i] + dp[j]);
                }
            }
        }
        int ma = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > ma) ma = dp[i];
        }
        cout << ma << endl;
    }
    return 0;
}