[백준] 가장 긴 바이토닉 부분 수열(11054)

문제 링크 : [백준] 가장 긴 바이토닉 부분 수열(11054)

문제 설명

임의의 k에 대하여,
S₁ < S₂ < ... S_k-1 < S_k > S_k+1 > ... SN-1 > S_N
위 조건을 만족하는 수열을 바이토닉 수열이라고 합니다.
주어진 수열에서 임의의 부분 수열을 뽑아냈을 때, 바이토닉 수열일 이루는 부분 수열 중 가장 긴 부분 수열의 길이를 출력하세요.

입력

N(수열의 갯수, 1 <= N <= 1,000)
A_i(수열의 값, 1 <= A_i <= 1,000)

10
1 5 2 1 4 3 4 5 2 1

출력

7

카테고리

#DP

시간 복잡도 상한

O(N²)

해결 방법

1. 오름차순과 내림차순을 동시에 고려하기는 너무 어렵습니다.
2. 특정 위치까지의 오름차순 길이, 그 위치부터의 내림차순 길이를 계산하여 두 길이를 더하면 될 것 같습니다.
3. 특정 위치까지의 오름차순, 특정 위치부터의 내림차순은 DP를 이용하여 O(N²)만에 구할 수 있습니다.
   3-1. D[i] = i번째로 끝나는 증가하는 부분 수열의 최장 길이
   3-2. D[i] = for(k = 1 to i-1)data[k]<data[i] 중 max(D[k])
4. 내림차순은 반대로 하면 됩니다.

시간복잡도

O(N²)

코드

#include<cstdio>
int n,d[1000],e[1000],f[1000],i,j,a;
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",d+i);
    e[0]=f[n-1]=1;
    for(i=1;i<n;i++){
        e[i]=1;
        for(j=0;j<i;j++){
            if(d[j]<d[i]&&e[j]+1>e[i])e[i]=e[j]+1;
        }
    }
    for(i=n-1;i>=0;i--){
        f[i]=1;
        for(j=n-1;j>i;j--){
            if(d[j]<d[i]&&f[j]+1>f[i])f[i]=f[j]+1;
        }
    }
    for(i=n-1;i>=0;i--)a=a<e[i]+f[i]?e[i]+f[i]:a;
    printf("%d",a-1);
}