백준 11055번 - C++

#include <bits/stdc++.h>
using namespace std;

int D[1005];
int S[1005];
int n;

// 1. 테이블 정의하기 : D[i] = i번째까지 증가부분수열의 최대 합
// 2. 점화식 정의하기 : D[k] = max(D[k],D[j]+S[k])
// 3. 초기값 정의하기  : 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> S[i];
		D[i] = S[i];
		for (int j = 1; j <= i; j++) {
			if (S[j] < S[i]) D[i] = max(D[i], D[j] + S[i]);
		}
	}
	cout << *max_element(D + 1, D + n + 1);
}