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

#include <iostream>

using namespace std;

const int MAXN = 1000 + 10;

int arr[MAXN];
int sum[MAXN];

int main () {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum[i] = arr[i];
	}
	int answer = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < i; j++){
			if (arr[i] > arr[j]){
				sum[i] = max(sum[i], sum[j] + arr[i]);
			}
		}
		answer = max(sum[i], answer);
	}
	cout << answer << endl;
	return 0;
}