[알고리즘/백준] 1912: 연속합(python)

쉬운 문제인데 40분이나 고민했다...

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	-2	19	18
	-4	-1	0	5	11	-24	-12	9	8
		3	4	9	15	-20	-8	13	12
			1	6	12	-23	-11	10	9
				5	11	-24	-12	9	8
					6	-29	-11	4	3
						-35	-23	-2	-3
							12	33	32
								21	20
									-1

모르겠어서 다 써봤다...
-4를 예로 들면 10까지 가장 큰 합은 10이고, -4까지는 두가지 경우가 있다. 10 -4 / -4
즉 자기 자신과 전의 가장 큰 합중에 max값을 구하면 된다.
max(dp[i-1]+a[i], a[i])

N = int(input())
a = list(map(int, input().split()))
dp = [0] * N
dp[0] = a[0]
for i in range(1, N):
    dp[i] = max(dp[i - 1] + a[i], a[i])
print(max(dp))