본문으로 바로가기

다이나믹 프로그래밍을 이용하여 각각의 증가 부분 수열의 합을 저장한 다음 가장 큰 합을 출력한다.

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

int dp[1001];
int a[1001];
int n;
priority_queue<int> pq;

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

  for (int i=1; i<=n; i++) {
    scanf("%d", &a[i]);
    dp[i] = a[i];

    for (int j=1; j<i; j++) {
      if (a[j] < a[i] && dp[i] < dp[j] + a[i]) {
        dp[i] = dp[j] + a[i];
      }
    }

    if (pq.empty() || pq.top() < dp[i]) {
      pq.push(dp[i]);
    }
  }

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

댓글을 달아 주세요