[python 파이썬] 백준 1912번 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

 

연속합을 스터디때 설명을 약간 들어서 그런지 거기서 얻은 아이디어로 문제를 풀었는데 맨땅에 헤딩식으로 풀었으면 못풀었을 것 같다. 

 

 

DP에서 생명은 점화식을 떠올릴 수 있느냐 없느냐다! 

(and 항상 저장을 하는 cache 공간이 필요)

n = int(input())

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