3장 다이나믹 프로그래밍 - (4) 문제 풀이 3 [11722번 - 가장 긴 감소하는 부분 수열]

#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[i]는 a[i]를 포함하는 가장 긴 감소하는 부분 수열의 길이

d[1] = a[1];

int max = 0;

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

d[i] = 1;

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

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

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

}

}

if (max<d[i])

max = d[i];

}

cout << max << endl;

return 0;

}