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

#include <cstdio>
#include <iostream>
using namespace std;
int a[1010];
int dp[1010];

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; ++i) {
			scanf("%d", &a[i]);
		}
		int answer = 0;
		for (int i = 0; i < n; ++i) {
			dp[i] = a[i];
			for (int j = 0; j < i; ++j) {
				if (a[j] < a[i]) {

					dp[i] = max(dp[i], dp[j] + a[i]);
				}
			}
			answer = max(answer, dp[i]);
		}

		printf("%d", answer);
	}
}