백준 1912번: 연속합 (파이썬)

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

1912번: 연속합

 

문제

 

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

 

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

 

첫째 줄에 답을 출력한다.

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

subsum 리스트는 수열의 동일 인덱스까지 포함하는 연속합의 최댓값을 저장하는 리스트다. 예시의 {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}를 보자. 10까지 포함하는 연속합은 하나의 경우 밖에 없으니 최댓값도 10이다. -4까지 포함하는 연속합의 최댓값은 6이다. 이는 10+(-4)와 -4를 비교하여 더 큰 값을 결정한 것이다. 3까지 포함하는 연속합의 최댓값은 9다. 이는 이전 인덱스까지의 연속합의 최댓값에 3을 더한 값과 3을 비교하여 더 큰 값을 결정한 것이다. 12까지 포함하는 연속합의 최댓값은 얼마일까? 이전 인덱스까지의 연속합의 최댓값은 -14다. -14+12와 12를 비교하였을 때 12가 더 크기 때문에, 12까지 포함하는 연속합의 최댓값은 12다. 이 방식에서 구현에 대한 힌트를 얻을 수 있다. 현재 인덱스의 값을 포함하는 연속합의 최댓값은, 이전 인덱스까지의 연속합의 최댓값에 이번 인덱스의 값을 더한 것과 이번 인덱스의 값 중 큰 값이다.구현은 간단하다. 리스트의 첫 번째 값은 수열의 첫 번째 값으로 초기화하고, 이후 이전 인덱스까지의 연속합의 최댓값에 이번 인덱스의 값을 더한 것과 이번 인덱스의 값 중 더 큰 값을 저장한다.

 

소스 코드

n = int(input())
seq = list(map(int, input().split()))

subsum = [seq[0]]
for i in range(1, n):
  subsum.append(max(subsum[i-1]+seq[i], seq[i]))
print(max(subsum))