[C/C++ 백준 11722번] 가장 긴 감소하는 부분 수열 (Silver 2)

www.acmicpc.net/problem/11722

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

유명한 dp문제.

dp[i]는 i번째 수를 포함하는 가장 긴 부분 수열의 개수이다.

모든 dp중 가장 큰수가 답.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N;
	scanf("%d", &N);
	int A[N], dp[N], ans = -1;
	for(int i=0; i<N; i++){
		scanf("%d", &A[i]);
		dp[i] = 1;
	}
	for(int i=0; i<N; i++){
		if(i==0)
			dp[i] = 1;
		else{
			for(int j=0; j<i; j++){
				if(A[j]>A[i])
					dp[i] = max(dp[i], dp[j]+1);
			}	
		}
		ans = max(ans, dp[i]);
	}
	printf("%d",ans);
}