[Python] 1912 연속합

문제

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

풀이과정

• 입력
  주어지는 정수의 개수 n
  n개의 정수들
  
• 출력
  연속된 수들중 최댓값

이전값과 연속해서 더하는데값이 더 작아질 경우 pass한다.
dp[i] = max(arr[i], dp[i-1] + arr[i])

	0	1	2	3	4	5	6	7	8	9
arr[i]	10	-4	3	1	5	6	-35	12	21	-1
dp[i-1] + arr[i]		10+(-4)	6 + 3	9 + 1	10 + 5	15 + 6	21 + (-35)	-14 + 12	12 + 21	33 + (-1)
dp[i]	10	6	9	10	15	21	-14	-2	33	32

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]

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