[백준 11054] 알고리즘 51일차 : 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054

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

동적계획법 C++

가장 긴 바이토닉 부분 수열 문제

 

접근 방법

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제

0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다.

증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데

여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이 다르다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n ;

    int num[n];
    int lengthasc[n];
    int lengthdesc[n];
    int result = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
    }
    for(int i = 0 ; i < n ; i++){
        lengthasc[i] = 1;
        for(int j = 0 ; j < i ; j++){
            if(num[j] < num[i] && lengthasc[j] >= lengthasc[i]){
                lengthasc[i] = lengthasc[j]+1;
            }
        }
    }
    
    for(int j = n-1 ; j >= 0 ; j--){
        lengthdesc[j] = 1;
        for(int k = j+1 ; k < n ; k++){
            if(num[j] > num[k] && lengthdesc[j] <= lengthdesc[k]){
                lengthdesc[j] = lengthdesc[k]+1;
            }
        }
    }

    for(int i = 0 ; i < n ; i++){
        if(result < lengthdesc[i]+lengthasc[i]-1)
            result = lengthdesc[i]+lengthasc[i]-1;
    }
    
    cout << result;
    
    return 0;
}