시행착오
- 처음에는 그냥 음수가 나오면 계산을 중단해서 합을 리스트에 저장하고, 다시 0부터 계산하는 식으로 했는데 모두 음수일 때도 문제가 되지만 음수가 있어도 누적합이 더 클 수도 있기 때문에 틀린 방법이었다.
- 그래서 연속합을 구했을 때 이전까지의 누적합보다 크지 않을 때 계산을 중단하면 된다고 생각했다가.. 이것도 아니다. 왜냐면 그 뒤에까지 더했을 때 또 더 클 수 있기 때문.
- 또한 처음부터 for문을 돌면 중간부터 더했을 때 값이 당연히 더 클 수 있는데 이걸 어떻게 고려하지? 했는데,,
- 리스트를 다 돌면서 i번째 원소가 여태의 누적합+원소값보다 더 크다면 이때 계산을 중단하면 된다! i+1번째 원소까지 더해도 당연히 'i번째 원소 + i+1번째 원소'값이 더 크기 때문이다.
코드
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
sum = 0
res = [num[0]]
for i in range(1, n):
res.append(max(num[i], res[i-1]+num[i]))
print(max(res))
결과
