백준 11054 - 가장 긴 바이토닉 부분 수열

출처 : www.acmicpc.net/problem/11054

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

 

고려사항

- lis 알고리즘 활용

- 가장 긴 증가하는 부분 수열 길이 구하고서,

num을 뒤집어서 다시 가장 긴 증가하는 부분 수열들 구하기 => 구한 배열을 뒤집으면, 가장 긴 감소하는 부분 수열 길이가 구해진다.

- asc[i] + dsc[i] - 1 이 최대가 되는 값 출력.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, ans = -1;
    int num1[1000], num2[1000], asc[1000], dsc[1000];
    cin>>n;
    for(int i=0;i<n;++i){
        cin >> num1[i];
        num2[i] = num1[i];
    }

    reverse(num2, num2+n);
    for(int i=0;i<n;++i){
        asc[i] = 1;
        dsc[i] = 1;
        for(int j=0;j<i;++j){
            if(num1[j] < num1[i]){
                asc[i] = max(asc[j]+1, asc[i]);
            }
            if(num2[j] < num2[i]){
                dsc[i] = max(dsc[j]+1, dsc[i]);
            }
        }
    }

    reverse(dsc, dsc+n);
    for(int i=0;i<n;++i){
        ans = max(ans, asc[i]+dsc[i]-1);
    }
    
    cout<<ans;
    return 0;
}