【正经题解】最大上升子序列和

#include <bits/stdc++.h>
#define N 1005

using namespace std;

int n, maxSum;  // 序列长度和最大上升子序列和
int a[N], dp[N]; // 原始序列和动态规划数组

void findMaxISum() {
    // 读取序列长度
    scanf("%d", &n);

    // 读取序列中的整数
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        dp[i] = a[i];
    }

    // 动态规划求最大上升子序列和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            // 判断当前位置的数是否能加入上升子序列，更新最大和
            if (a[i] > a[j] && dp[i] < dp[j] + a[i]) {
                dp[i] = dp[j] + a[i];
            }
        }
        maxSum = max(maxSum, dp[i]);
    }

    // 输出结果
    printf("%d", maxSum);
}

int main() {
    // 调用函数处理序列
    findMaxISum();
    return 0;
}