11054번

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

D[N] N을 제일 끝으로 하는 감소하는 가장 긴 부분 수열의 길이

U[N] N을 시작으로 하는 감소하는 가장 긴 부분 수열의 길이

로 점화식을 세웠다.

증가하는 가장 긴 부분 수열의 길이를 구하는 문제 11053번과

감소하는 가장 긴 부분 수열의 길이를 구하는 문제 11722번의 짬뽕이라고 생각하고

두 문제를 합쳐서 풀었다.

goUp()과 goDown() 함수를 나눠서 각자 다른 값을 구하도록 하였고,

중복되는 값 1개를 정답에서 빼주면서 정답을 구했다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int A[1001];
int D[1001];
int U[1001];
int ans;
int N;
int goDown(int n)
{
    if (D[n] != 1)
    {
        return D[n];
    }
 
    for (int i = 1; i < n; i++)
    {
        if (A[i] < A[n])
        {
            D[n]=max(D[n],goDown(i)+1);
        }
    }
 
    return D[n];
 
}
int goUp(int n)
{
    if (U[n] != 1)
    {
        return U[n];
    }
 
    for (int i = n+1;i <= N; i++)
    {
        if (A[i] < A[n])
        {
            U[n] = max(U[n], goUp(i) + 1);
        }
    }
 
    return U[n];
 
}
 
int main()
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i];
        D[i] = 1;
        U[i] = 1;
    }
 
    for (int i = 1; i <= N; i++)
    {
        ans =max(ans,goDown(i)+goUp(i)-1);
    }
 
    cout << ans << endl;
    return 0;
}