BOJ 11054 가장 긴 바이토닉 부분 수열

 

문제 링크 : https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

 

가장 긴 단봉(unimodal) 수열, 즉 증가하다가 감소하는 수열의 길이를 구해야 한다. (증가수열, 감소수열은 허용된다.)

arr 의 index 는 1 부터 N 까지.

최대 부분 감소 수열을 구할 수 있으면 충분하다.

 

원소가 하나인 수열을 생각하면, dp 의 초기값은 모두 1 이다. 

dp[0][i] = ( i 에서 끝나는  최대 부분 증가 수열의 길이 )

dp[1][i] = ( i 에서 시작되는 최대 부분 감소 수열의 길이 )

 

loop 하나에 몰아 넣어서 처리했다.

 

전체 코드는 다음과 같다.

 

#include<bits/stdc++.h>

using namespace std;

int N, arr[1001], dp[2][1001];

int main(){
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d",&arr[i]);  
    for(int k=0;k<2;k++) for(int i=1;i<=N;i++) dp[k][i]=1;
            
    for(int i=1;i<N;i++) {
        for(int j=i+1;j<=N;j++){
            if(arr[i]<arr[j])
                dp[0][j]=max(dp[0][j], dp[0][i]+1);
            if(arr[N+1-i]<arr[N+1-j])
                dp[1][N+1-j]=max(dp[1][N+1-j], dp[1][N+1-i]+1);
        }
    }
    
    int ans=0;
    for(int i=1;i<=N;i++) ans=max(ans, dp[0][i]+dp[1][i]);
    
    printf("%d\n",ans-1);
}