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

#include<iostream>
#include<climits>
using namespace std;

int arr[1005];
int dp[1010] = { 0 };

int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		int answer = 0;

		for (int i = 0; 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]);
		}
		cout << answer << endl; 

	}

}