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

#include <bits/stdc++.h>

using namespace std;
int dp[1001];

int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        int arr[N];
        for (int i = 0; i < N; ++i) {
            scanf("%d", &arr[i]);
        }
        dp[0] = arr[0];
        int answer = 0;
        for (int i = 1; i < N; ++i) {
            dp[i] = arr[i];
            for (int j = 0; j < i; ++j) {
                if (arr[j] < arr[i]) {
                    dp[i] = max(dp[i], dp[j] + arr[i]);
                }
            }
            answer = max(answer, dp[i]);    //dp数组的最大值
        }
        printf("%d\n", answer);
    }
    return 0;
}