3장 다이나믹 프로그래밍 - (4) 문제 풀이 2 [11053번 - 가장 큰 증가하는 부분 수열]

#include <iostream>

using namespace std;

int d[1001];

int a[1001];

int main(void) {

int n;

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

}

d[1] = a[1];

int max = 0;

for (int i = 2; i <= n; i++) {

d[i] = a[i];

for (int j = 1; j < i; j++) {

if (a[j] < a[i] && d[i]<d[j]+a[i]) {

d[i] = d[j] + a[i];

}

}

if (max < d[i])

max = d[i];

}

cout << max << endl;

return 0;

}