[백준] 1912. 연속합 풀이

https://www.acmicpc.net/problem/1912

 

n개의 정수 수열을 받고, 연속된 수를 선택해서 가장 큰 값을 찾아내야 하는 문제이다.

 

우선, 선택할 수 있는 숫자의 개수는 제한이 없으므로 양수가 연속되어있다면 '무조건' 모두 선택해야한다.

이때 문제는 음수가 중간에 있더라도 이를 감안할 수 있는지를 확인하는 것이다.

 

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

 

문제에서 제시한 것 처럼 위와같은 수열이 있다고 해보자.

 

우선 10을 선택해보자.

그 다음 숫자는 음수이고, 그 다음 숫자는 양수이다.

만약 음수 때문에 10에서 선택을 멈추면 3, 1, 5, 6까지 선택하여 더 큰 값을 만들어내는 상황을 만들지 못한다.

 

따라서 우선 10과 -4를 선택을 해보고 이 값의 합이 양수라면 다음에 오는 양수들을 선택하는 방식으로 가야한다.

 

즉,

왼쪽부터 차례로 검사할 때 이전에 선택된 숫자들의 합과 현재 검사하는 숫자와의 합이 음수라면 다시 현재 숫자에서부터 선택을 시작하고

양수라면 선택을 이어나가는 방식으로 해결할 수 있다. (다시 숫자를 선택하려는 시점에서 이전에 선택된 숫자들의 합에 대해 결과 출력을 위한 최댓값 갱신이 이루어져야 한다.)

 

 

 

---

C

#include <stdio.h>
int d[100001];

int main() {
    int n; scanf("%d", &n);
    int num[n];
    for(int i = 0; i < n; i++) scanf("%d", &num[i]);

    d[0] = num[0];
    int max = d[0];
    for(int i = 1; i < n; i++){
        if(d[i-1] < 0) d[i] = num[i];
        else d[i] = d[i-1] + num[i];
        if(d[i] > max) max = d[i]; // 최댓값 갱신
    }
    printf("%d", max);
}

---

Python

d = [0 for _ in range(1000001)]
n = int(input())

num = [0 for _ in range(n)]
num = list(map(int, input().split()))

d[0] = num[0]
maxV = d[0]
for i in range(1, n):
    if d[i-1] < 0: d[i] = num[i]
    else: d[i] = d[i-1] + num[i]
    if d[i] > maxV: maxV = d[i]
print(maxV)