[DP] 1912번 - 연속합 (48일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#숫자 개수 입력
n = int(input())

#수열과 각 숫자까지의 최대 연속합을 저장하는 dp 선언
string = list(map(int, input().split()))
dp = [0 for _ in range(n)]

#dp의 첫 값을 수열 첫 숫자로 초기화
dp[0] = string[0]

#2번째~마지막 숫자까지
for i in range(1, len(string)):
    #각 숫자를 연속합으로 시작하는 경우와 이전 숫자에 이어서 연속합을 취하는 것 중
    #더 합이 큰 값을 dp에 순차적으로 저장
    dp[i] = max(dp[i-1] + string[i], string[i])

#dp 기록값 중 가장 큰 값 출력
print(max(dp))

#인사이트
#DP는 언제나 탐색 순서, 문제 해석에 기반한 점화식 작성이 우선시되어야 함