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

 11053번을 풀면 쉽게 풀 수 있는 DP문제.

 

 1. 0부터 N-1까지 증가하는 부분 수열을 구한다.

 2. N-1부터 0까지 증가하는 부분 수열을 구한다.

 3. 0부터 N-1까지 구한 두 부분 수열의 값을 더하면서 최댓값을 찾는다. (가장 긴 바이토닉 부분 수열이다)

 4. 이때 해당 원소가 중복되기 때문에 최댓값에서 -1을 해준다.

      ex)  num ->   1 2 3 2 1

               dp1 ->   1 2 3 2 1

              dp2 ->   1 2 3 2 1

       dp1+dp2 = 6(최댓값), 원소 3이 중복되므로 -1, 정답은 5.

 

#include <iostream>
#define MAX 1001
using namespace std;
 
int dp1[MAX];
int dp2[MAX];
int num[MAX];
int N;
 
void solved(){
    for(int i=0;i<N;i++){
        dp1[i]=1;
        for(int j=0;j<i;j++){
            if(num[i]>num[j]){
                dp1[i]=max(dp1[i],dp1[j]+1);
            }
        }
    }
    
    for(int i=N-1;i>=0;i--){
        dp2[i]=1;
        for(int j=N-1;j>i;j--){
            if(num[i]>num[j]){
                dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
    }
    
    int ans=0;
    
    for(int i=0;i<N;i++){
        ans=max(ans,dp1[i]+dp2[i]);
    }
    
    cout << ans-1 << endl;
}
 
int main(){
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> num[i];
    }
    
    solved();
}