最大上升子序列和

最长递增子序列的变形问题。

// runtime: 4ms
// space; 496K
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 1000;

int arr[MAX];
int dp[MAX]; // 以arr[i]为结尾的最大上升子序列和

int MaxIncSubsequence(int k) {
    int sum = 0;
    for (int i = 0; i < k; ++i) {
        dp[i] = arr[i];

        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
        sum = max(sum, dp[i]);
    }
    return sum;
}

int main() {
    int k;
    while (scanf("%d", &k) != EOF) {
        for (int i = 0; i < k; ++i) {
            scanf("%d", &arr[i]);
        }

        printf("%d\n", MaxIncSubsequence(k));
    }
    return 0;
}