[BOJ] 1912 : 연속합 (Python3)

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

풀이

dp 배열을 만들어 i번째 원소에 해당 원소를 마지막으로 하는 가장 큰 연속합을 저장한다.
dp의 가장 최근 원소와 순서가 되는 lst[i] 원소를 더하면 새로운 연속합이 만들어진다. (lst[0]은 dp에 원소가 없으므로 미리 추가해둠)
그러나 이것이 가장 큰 연속합이 되지 않는 경우가 있다.
dp[-1] + lst[i]가 음수일 경우, 자기 자신이 더 큰 연속합이 된다.

때문에 dp에는 dp[-1] + lst[i]와 lst[i] 중 최댓값을 추가한다.
dp 배열에 있는 수 중 max 값을 찾으면 가장 큰 연속합을 구할 수 있다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().strip().split()))
dp = [lst[0]]

for i in range(1, n):
    dp.append(max(dp[-1] + lst[i], lst[i]))

print(max(dp))