본문으로 바로가기

다이나믹 프로그래밍을 이용하여 LISLDS를 구한 다음 바이토닉 수열의 합 중 최대값을 출력한다.

#include <cstdio>
#include <queue>
using namespace std;

int dp1[1001];
int dp2[1001];
int a[1001];
int n;
priority_queue<int> pq;

int main() {
  scanf("%d", &n);

  // LIS
  for (int i=1; i<=n; i++) {
    scanf("%d", &a[i]);
    dp1[i] = 1;
    for (int j=1; j<i; j++) {
      if (a[j] < a[i] && dp1[i] < dp1[j]+1) {
        dp1[i] = dp1[j]+1;
      }
    [BOJ] 11054: 가장 긴 바이토닉 부분 수열
  }

  // LDS
  for (int i=n; i>=1; i--) {
    dp2[i] = 1;
    for (int j=n; j>i; j--) {
      if (a[j] < a[i] && dp2[i] < dp2[j]+1) {
        dp2[i] = dp2[j]+1;
      }
    }

    // 바이토닉 수열의 최대값을 구한다
    int x = dp1[i] + dp2[i] - 1;
    if (pq.empty() || x > pq.top()) {
      pq.push(x);
    }
  }

  printf("%d\n", pq.top());
  return 0;
}

댓글을 달아 주세요