백준 1912번: 연속합 (Python)

접근

DP 문제로써 dp[i]에

1. 직전까지의 부분합 dp[i - 1]과 현재 값 m[i]를 더한 값
2. 현재 값 m[i]

를 비교하여 둘 중 큰 값을 저장함으로써 문제를 해결할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
m = [0] + list(map(int, sys.stdin.readline().split()))
dp = [-1001 for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i] = max(dp[i - 1] + m[i], m[i])
print(max(dp))

더 생각해 볼 것?

...