[백준] 1912번: 연속합 - C++

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에 답을 출력한다.

---

DP를 이용하여 풀 수 있는 문제. 앞서 풀었던 LIS 문제들에서 조금만 응용하면 풀 수 있다.

n까지의 수열인 A[]와 부분합을 기록하는 배열 D[]를 선언한다. 전체를 돌면서 (i - 1)까지의 최대가 되는 부분합(D[i - 1])에 A[i]를 더한 임시 최대 부분합과 A[i] 자기 자신의 값을 비교한 뒤, A[i]가 더 크다면 지금까지의 부분합은 모두 버려지고, A[i]부터 다시 시작하여 부분합을 구한다. 그리고 현재 최댓값으로 기록되어있는 값과 비교하여 최대 합을 갱신한다. 이를 다시 순서대로 표현하자면 다음과 같다.

 

1. D[i] 기록

    1-1. A[i] ≤ D[i - 1] + A[i], D[i] = D[i - 1] + A[i]

    1-2. A[i] > D[i - 1] + A[i], D[i] = A[i]

2. 기존의 최댓값과 비교하여 최대합 기록

 

코드

#include <cstdio>
#include <vector>

using namespace std;

int DP(int num);
int max(int a, int b) { return a > b ? a : b; }

int main(void) {
    int n;
    scanf("%d", &n);
    printf("%d\n", DP(n));
    return 0;
}

int DP(int num) {
    vector<int> A(num + 1, 0);
    vector<int> D(num + 1, 0);

    for(int i = 1; i <= num; i++) {
        scanf("%d", &A[i]);
    }

    int result = A[1];

    for(int i = 1; i <= num; i++) {
        D[i] = max(A[i], D[i - 1] + A[i]);
        result = max(result, D[i]);
    }

    return result;
}