백준 1921번: 연속합 (Python)

문제

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

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

해설

 다이나믹 프로그래밍을 활용해 풀 수 있는 문제다. '연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합' 을 구해야 한다. 따라서 DP[i] 는 'i번째까지의 수열에서 구할 수 있는 최대 연속합' 을 저장하게끔 만들어야 한다.

 

연속합이 만들어지는 경우는 다음 세 가지 경우이다.

• 이전 최장 연속합과 연결
• 자신 바로 앞 원소(i-1)와 연결
• 자신 그 자체

아래 테스트 케이스에 대한 DP 테이블을 보며 이해해보자.

10
10 -4 3 1 5 6 -35 12 21 -1

DP[i]는 i번째 인덱스에서 연속합이 만들어지는 세 가지 경우 중 가장 큰 값을 저장한다. 이 DP값은 다음 인덱스에서 '(1) 이전 최장 연속합과 연결' 될 때 비교를 위해 사용된다. 

 

이렇게 DP 테이블을 구성한 뒤, 가장 큰 값을 골라 출력하면 된다.

 

코드

N = int(input())
arr = []
arr = list(map(int, input().split()))

DP = [0] * N
DP[0] = arr[0]

for i in range(1, len(arr)):
    DP[i] = max([DP[i-1] + arr[i], arr[i-1] + arr[i], arr[i]])

print(max(DP))