백준 1912번: 연속합

백준 1912번: 연속합

아이디어

배열의 첫 번째 원소부터 합을 기록한다. 그 합이 음수가 되는 순간 그 다음 원소는 음수에다가 더하지 않고 다시 처음부터 합을 기록한다. 계속 더해 나가는 것보다 시작점을 바꾸는 것이 이득이기 때문이다. 이렇게 기록된 합중에 가장 큰 값이 정답이다.

다음과 같이 연속 합이 -1이 되는 지점 바로 다음을 시작점으로 해야 합이 최대가 된다.

코드

N = int(input())
arr = list(map(int, input().split()))
d = [arr[0]] + [0]*(N - 1)

for i in range(1, N):
    if d[i - 1] < 0:
        d[i] = arr[i]
    else:
        d[i] = d[i - 1] + arr[i]

print(max(d))

여담

1년 반 전에 풀다가 포기했던 문제다. 2020년 1월 겨울에 같은과 선배가 공부하자고 해서 중앙도서관 가서 풀었던 기억이 있다. 그때 처음으로 C언어 공부를 시작해서 뭐가 뭔지도 모르고 그냥 몇시간동안 들이박았는데 지금 생각해보면 그냥 웃음밖에 안나온다.