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

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


$O(n^2)$

dp0[i]:증가하는 도중의 최장 증가 수열 길이
dp1[i]:감소하는 도중의 최장 바이토닉 수열 길이

두 점화식을 풀어 답을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1001], dp[2][1001], r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        for (int j = 0; j < i; j++)
            if (a[i]>a[j]) dp[0][i] = max(dp[0][i], dp[0][j] + 1);
            else if (a[i]<a[j]) dp[1][i] = max({ dp[1][i],dp[0][j] + 1,dp[1][j] + 1 });
            r = max({ r,dp[0][i], dp[1][i] });
    }
    printf("%d", r);
    return 0;
}