가장 긴 바이토닉 부분 수열

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

간단한 DP를 2번 돌려서 풀 수 있는 문제이다.

• INCR[i]: NUMBER[i]에서 끝나는 최장 부분 증가 수열

• DECR[i]: NUMBER[i]에서 시작하는 최장 부분 감소 수열

자명하게 답은 max(INCR[i] + DECR[i] - 1)이 된다.

#include <iostream>
#include <algorithm>

using namespace std;

const int kMaxN = 1000;

int N;
int ARR[kMaxN];
int INCR[kMaxN];
int DECR[kMaxN];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;
  for (int i = 0; i < N; ++i)
  {
    cin >> ARR[i];
  }

  INCR[0] = 1;
  DECR[N - 1] = 1;

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

  for (int i = N - 2; i >= 0; --i)
  {
    DECR[i] = 1;
    for (int j = N - 1; j > i; --j)
    {
      if (ARR[i] > ARR[j])
      {
        DECR[i] = max(DECR[i], DECR[j] + 1);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < N; ++i)
  {
    ans = max(ans, INCR[i] + DECR[i] - 1);
  }

  cout << ans << '\n';

  return 0;
}