greentea31's Note

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

풀이 과정

시간 제한 1초에 n이 최대 100,000이므로 브루트 포스로 합을 일일이 다 구하면 시간제한 내에 문제를 해결할 수 없을 것이다.

d[i] = i를 마지막으로 하는 가장 큰 연속합이라고 하자.

가장 큰 연속합을 구하기 위해서 맨 앞에서 부터 숫자를 쭉 더해나가되, 연속합이 0보다 작아지는 순간 기존의 수들의 합은 버리고 새로운 수부터 합을 구하는게 더 값이 커질 것임을 알 수 있다.

따라서 d[i] = d[i-1] + a[i] (d[i-1] > 0)

                  = A[i] (d[i-1] <= 0)

이라는 점화식이 성립하고 이를 통해 문제를 해결할 수 있다

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A.insert(0, 0)
d = [-1001 for _ in range(n+1)]
d[1] = A[1]

for i in range(2, n+1):
    d[i] = d[i-1] + A[i] if d[i-1] > 0 else A[i]

print(max(d))