[C++]BOJ 11055 - 가장 큰 증가 부분 수열

가장 긴 증가하는 부분 수열 문제에서 dp[]에 길이를 넣었다면 지금 이 문제는 최대값을 넣으면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1001], dp[1001];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = arr[i];
		for(int j = 1; j < i; j++)
			if(arr[j] < arr[i]) dp[i] = max(dp[j] + arr[i], dp[i]);
	}
	sort(dp, dp + n + 1);
	cout << dp[n];
}