아카이빙/BOJ

백준 1912번 - 연속합

셩님 2017. 7. 15. 16:11

백준 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의 최대 값


'아카이빙 > BOJ' 카테고리의 다른 글

백준 2580번 - 스도쿠  (2) 2017.07.19
백준 9663번 - N Queen  (0) 2017.07.19
백준 10844번 - 쉬운 계단 수  (2) 2017.07.15
백준 2156번 - 포도주 시식  (2) 2017.07.15
백준 2293번 - 동전1  (5) 2017.07.15