문제

image.png

image.png

풀이

점화식 정의

dp[n] = n번째 까지의 가장 긴 감소하는 부분 수열의 길이

if : a[n-1] > a[n] && dp[i-1] > dp[i] 이면, dp[n-1] + dp[n= 이 성립됨(n-1번째 값이, 현재값 보다 작다면 가장 긴 감소하는 부분수열에 연결)
else : 새로운 부분 수열을 만들어야 한다? 어떻게?
a = 10,30,10,20,20,10
d = 1, 1, 2, 2, 2, 3

코드


/*
 점화식 정의
 dp[n] = n번째 까지의 가장 긴 감소하는 부분 수열의 길이
 if : a[n-1] > a[n] && dp[i-1] > dp[i] 이면, dp[n-1] + dp[n= 이 성립됨(n-1번째 값이, 현재값 보다 작다면 가장 긴 감소하는 부분수열에 연결)
 else : 새로운 부분 수열을 만들어야 한다? 어떻게?
 a = 10,30,10,20,20,10
 d = 1, 1, 2, 2, 2, 3
 */
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1001];
int a[1001];
int main() {

    int n,ans=-2147000000;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        dp[i] = 1;
    }

    for(int i = 1; i<= n; i++) {
        for(int j = 1; j<= i; j++) {
            if(a[j] > a[i] && dp[j] + 1  > dp[i]) {
                dp[i] = max(dp[j],dp[i]) + 1;
            }
        }

        if(dp[i] > ans) ans = dp[i];
    }

    printf("%d\n",ans);
    return 0;
}