백준 13398 파이썬 python : 연속합 2 @@황소처럼 우직하게@@ 쉬버..

차원이 갈리는 다이나믹 유형

n = int(input())
lst = list(map(int, input().split()))

dp = [[0, 0] for i in range(n)]
dp[0] = [lst[0], -999999999]

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

ans = -999999999
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)