연속합 풀이

문제 링크: https://www.acmicpc.net/problem/1912

백준 알고리즘 기초 1/2 400에서 12번째 - 1912번 연속합을 풀어보았다.

 

풀이: 동적 계획법은 현재 상태와 전 상태를 비교하는 과정이 정말 중요한 거 같다.

 

C++

 

Python

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

Java