1912번 - 연속합(python3)

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

 

동적 계획법을 이용한 연속합을 구하는 문제입니다. n개의 정수로 이루어진 배열이 주어지면, 그 중 연속된 숫자들의 합이 최대가 되는 경우를 구하면 됩니다.

 

sumlist라는 리스트에는 특정 숫자를 훑는 순간 부분수열의 합이 저장되는데, 현재 보고 있는 k번째 숫자가 양수인지 음수인지에 따라 새로운 부분수열의 합을 저장할 지, 아니면 이전까지의 부분수열의 합에 k번째 숫자를 더한 값을 업데이트할 지가 결정됩니다.

 

maxn은 모든 부분수열의 합 중 최댓값을 저장하고, for문이 끝난 뒤의 maxn이 정답이 됩니다.

 

n = int(input())
maxn = -1001 #초기 최댓값
numlist = list(map(int, input().split()))
sumlist = [0]

for i in range(n):
    #k번째 숫자가 음수라면 numlist[i] > numlist[i]+sumlist[i]    
    sumlist.append(max(numlist[i], numlist[i]+sumlist[i]))
    
    #현재 상태의 최댓값과 이전까지의 최댓값 비교
    maxn = max(maxn, sumlist[i+1])

print(maxn)