1912번: 연속합

import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int,input().split()))
dp = li

for i in range(1,n):
    dp[i] = max(dp[i], dp[i-1] + li[i])

print(max(dp))

n 개의 수를 리스트 li에 저장하고 li 와 동일한 리스트 dp 를 만들어준다.

dp 에는 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이 들어갈 것이다.

n == 1일 경우 dp[0]을 출력하면 되기에 범위는 1부터 시작한다.

dp[ i - 1 ]이 음수일 경우 dp[ i ]부터 새롭게 연속된 수를 시작하면 되기에 dp[ i ],
dp[ i - 1 ]이 양수일 경우 li[ i ]와 더해준 값 dp[ i - 1 ] + li[ i ]
그 후 둘 중 더 큰 값을 dp[ i ]로 잡아준다.

그렇게 리스트 dp를 모두 채우고 max(dp)를 출력해준다.