백준 1912번 - 연속합

백준 1912번 - 연속합

문제

• n개의 정수로 이루어진 임의의 수열이 주어진다.

• 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.

• 단, 숫자는 한 개 이상 선택해야 한다.

• 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.

• 여기서 정답은 12+21인 33이 정답이 된다.

입력

• 첫째 줄에 정수 n(1≤n≤100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.

• 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

• 첫째 줄에 답을 출력한다.

예제 입력

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력

33

접근

• Dynamic Programming으로 접근한다.

• 첫 번째 정수까지의 최대 연속 부분 합을 구한다. 당연히 그 값 그대로.

• 두 번째 정수까지의 최대 연속 부분 합을 구한다.

• n 번째 정수까지의 최대 연속 부분 합을 구한다.

• n 번째 정수까지의 최대 연속 부분 합을 D(n)이라고 하자.쉽게 생각했을 때, D(n)은 D(n-1) + n 번째 정수이다.그러나, D(n-1) + n이 n보다 작다면 n을 더해나가는 게 의미가 없다.이 경우에는 D(n)은 n이 된다.

점화식

• ​ : i번째 정수

• ​ : i번째 정수까지 최대 연속 부분 합

• 여기서, 정답은 ​이다.

풀이

1) 첫 번째 정수까지의 최대 연속 부분합

C(i) = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
D(i) =
    i   0   1   2   3   4   5   6   7   8   9
        10  0   0   0   0   0   0   0   0   0

2) 두 번째 정수까지의 최대 연속 부분합

D(i) =
    i   0   1   2   3   4   5   6   7   8   9
        10  6   0   0   0   0   0   0   0   0

3) 세 번째 정수까지의 최대 연속 부분합

D(i) =
    i   0   1   2   3   4   5   6   7   8   9
        10  6   9   0   0   0   0   0   0   0

4) 네 번째 정수까지의 최대 연속 부분합

D(i) =
    i   0   1   2   3   4   5   6   7   8   9
        10  6   9   10  0   0   0   0   0   0

5) 10번 째 정수까지의 최대 연속 부분합

D(i) =
    i   0   1   2   3   4   5   6   7   8   9
        10  6   9   10  15  21  -14 12  33  32

C++ Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
​
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> c(n, 0);
    vector<int> d(n, 0);
​
    int ret = -1000;
​
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
​
    d[0] = c[0];
    for (int i = 1; i < n; i++) {
        d[i] = max(d[i - 1] + c[i], c[i]);
        ret = max(ret, d[i]);
    }
    ret = max(ret, d[0]);
​
    printf("%d\n", ret);
​
    return 0;
}

• ret은 벡터 d의 최대 값