연속합 - 백준 1912번

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

 dp문제인데 왼쪽부터 더해주면서 큰수가 나올경우 dp배열에 넣어준다.

import sys

N=int(sys.stdin.readline())
M=list(map(int,sys.stdin.readline().split()))

dp=[0]*N
dp[0]=M[0]

for i in range(1,N):
    dp[i]=max(M[i],dp[i-1]+M[i])
    
print(max(dp))

 

 왼쪽부터 숫자 하나씩 비교하면서 만약 i-1 까지의 누적합의 최대값+ 현재 i의 배열값보다 현재 i의 배열값이 더 크면 현재 i의 배열값을 dp배열에 넣는다.

 이 의미는 i-1까지에서 찾은 누적합의 최댓값보다 지금 i의 배열값이 더 크기때문에 i부터 새로운 누적합을 찾겠다는 의미이다.