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

//11054 - 가장 긴 바이토닉 부분 수열
 
#include <iostream>
using namespace std;
 
int N;
int arr[1000];
int cache[1000];
int cache2[1000];
 
void init()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cache[i] = cache2[i] = -1;
        cin >> arr[i];
    }
}
 
int dp(int idx)
{
    int &ret = cache[idx];
    if (ret != -1)
        return ret;
    ret = 0;
    for (int i = idx + 1; i < N; ++i)
        if (arr[idx] > arr[i])
            ret = max(ret, dp(i));
    ++ret;
    return ret;
}
 
int dp2(int idx)
{
    int &ret = cache2[idx];
    if (ret != -1)
        return ret;
    ret = 0;
    for (int i = idx - 1; i >= 0; --i)
        if (arr[idx] > arr[i])
            ret = max(ret, dp2(i));
    ++ret;
    return ret;
}
 
int main()
{
    init();
    int ans = 0;
    for (int i = 0; i < N; ++i)
        ans = max(ans, dp(i) + dp2(i) - 1);
    cout << ans;
}

 

 

 

 

 

 

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

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

 

 

 

 

 

 

가장 긴 바이토닉 부분 수열

DP문제

dp(idx) : idx에서 시작해 우로 감소하는 부분수열중 가장 긴 것의 길이

dp2(idx) : idx에서 시작해 좌로 감소하는 부분수열중 가장 긴 것의 길이

 

dp(idx) + dp2(idx)중 가장 큰것이 정답입니다!