[C++] 백준 11055번 - 가장 큰 증가 부분 수열

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
int a[1001];
long long dp[1001];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	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] < dp[j] + a[i]) {
				dp[i] = dp[j] + a[i];
			}
		}
	}
	
	int m = *max_element(dp, dp + n);
	cout << m << endl;

	return 0;
}