1912 - 연속합

1) 문제 설명

주어진 수들 가운데, 연속적으로 더했을때 가장 큰 수를 찾는 문제

전형적인 dp 문제

 

특정 위치에서 연속합은 내 앞에껄 가져와서 더하거나 혹은 나만 더하거나 이다. 

 

dp[0]은 list[0]과 같고 

dp[1] = max(dp[0] + list[1] , list[1])

dp[2] = max(dp[1] + list[2] , list[2])

 

점화식을 세워보면

dp[n] = max(dp[n-1] + list[n] , list[n]) 이다

 

2) 문제 풀이

 

import sys

n = int(input())
lst = list(map(int, sys.stdin.readline().split()))
dp = [0] * (n)

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