BOJ 11055 가장 큰 증가 부분 수열

boj 11055 가장 큰 증가 부분 수열

boj 11053 가장 긴 증가하는 부분 수열과 풀이가 비슷한 문제이다. 다만 11053에서는 길이였다면 이번 문제에서는 수열의 합이 최대가 되어야한다. D[i]는 i번째 원소를 마지막으로 하는 증가 부분 수열의 합 중 최댓값이라고 정의한다. a[i]는 수열을 담는 배열이다. 문제에서 주어진 수열을 예시로 들자면, 아래와 같이 작동해야한다.

코드를 먼저 보고 코드에 대해 설명하겠다.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[1005];
int D[1005];
int mx;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        D[i] = a[i];

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

    for (int i = 1; i <= n; i++) mx = max(mx, D[i]);

    cout << mx;
}

D[i]는 합이므로 초기 값은 a[i]로 초기화해준다. D[i] = D[j] + a[i]의 형태로 점화식이 정해지는데, 이것이 실행되는 조건이 이 문제의 핵심이다.

• a[i] > a[j] (단, i > j)
  : 증가하는 수열이므로 위 조건을 만족해야만 한다.
• D[i] < D[j] + a[i]
  : 위 조건을 만족하지 않으면 어떤 상황이 일어나는지 보자. i가 4이고 j가 2인 경우를 막 지나서 아래와 같은 상황이다.
  

  

D[i] < D[j] + a[i]라는 조건이 없으면, j가 3인 경우를 지나면서 아래와 같이 D[i]가 변하는 문제가 생긴다.

그러므로 위 두 조건을 만족해야만 한다.