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

www.acmicpc.net/problem/11054

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

hackids.tistory.com/26

[백준/C,C++] 11053번: 가장 긴 증가하는 부분 수열

11503번: 가장 긴 증가하는 부분 수열 문제와 비슷한 LIS 문제입니다만.. 훨씬 어려웠던 것 같습니다. 바이토닉 수열은 증가하는 수열이거나 감소하는 수열이거나 증가하다가 감소하는 수열이어야 합니다. 11503번처럼 증가하는 수열을 구하는 것은 해당 문제를 풀었다면 크게 어렵지 않은 과정입니다. 감소하는 수열도 반복문을 거꾸로 돌리면 되기에 어렵지 않죠. 이 문제에서 가장 중요한 것은 각 인덱스에서 증가하는 수열과 감소하는 수열의 길이를 합쳐 가장 긴 곳을 찾아야 합니다. 예제 입력인 1, 5, 2, 1, 4, 3, 4, 5, 2, 1을 살펴보겠습니다.

	1	5	2	1	4	3	4	5	2	1
증가	1	2	2	1	3	3	4	5	2	1
감소	1	5	2	1	4	3	3	3	2	1
바이토닉	2	7	4	2	7	6	7	8	4	2

표를 보면 가장 긴 바이토닉 부분 수열의 길이는 7이고 5가 그 꼭짓점이 됩니다.

#include<iostream>

using namespace std;

#define MAX 1001

int seq[MAX];
int DP[MAX][2];
int res;

int main(void)
{
    int N; cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> seq[i];
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (seq[i] > seq[j]) {
                DP[i][0] = max(DP[i][0], DP[j][0] + 1);
            }
        }
    }

    for (int i = N; i >= 1; i--) {
        for (int j = N + 1; j > i; j--) {
            if (seq[i] > seq[j]) {
                DP[i][1] = max(DP[i][1], DP[j][1] + 1);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (res < DP[i][0] + DP[i][1]) {
            res = DP[i][0] + DP[i][1];
        }
    }

    cout << res - 1;

    return 0;
}