[백준/DP/C++] 11054번 가장 긴 바이토닉 부분 수열

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

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

일단 아이디어는 수열 중 하나를 기준으로 잡고
왼쪽으로는 가장 긴 증가하는 부분수열, 오른쪽으로는 가장 긴 감소하는 부분수열을 계산하려고 했다

동시에 하려다 보니 복잡했는데 따로따로 구해서 더해도 똑같다는 생각이 들어서 그렇게 구현했다

포인트는 두 수열에 모두 자신이 포함되다보니 마지막에 1을 빼줘야한다는 것이다

#include <bits/stdc++.h>

using namespace std;
int n;
int lis[1001] = {0},lds[1001] = {0}, a[1001] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        lis[i] = 1;
        lds[i] = 1;
    }
    // 가장 긴 증가하는 부분 수열
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(a[i]>a[j])
                lis[i] = max(lis[i], lis[j]+1);
        }
    }
    // 가장 긴 감소하는 부분 수열
    for(int i=n-1; i>=1; i--){
        for(int j=n; j>i; j--){
            if(a[i]>a[j])
                lds[i] = max(lds[i], lds[j]+1);
        }
    }

    int result = 0;
    for(int i=1; i<=n; i++){
        result = max(result, lis[i]+lds[i]-1);
    }
    cout << result << endl;

    return 0;
}