백준 11722 : 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

바로 이전 포스팅 11055번과 비슷한 유형의 문제였습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n, a[1001], dp[1001] = { 0, 1 }, s = 1;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 2; i <= n; i++) {
		dp[i] = 1;
		for (int j = i-1; j >= 0; j--)
			if (a[j] > a[i]) dp[i] = max(dp[i], 1 + dp[j]);
		s = max(dp[i], s);
	}
	printf("%d", s);
}