[백준/Python] 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배열을 이용한다. 이 때 dp[n]의 의미는 n번째 원소를 포함한 연속 부분합 중 최대값을 뜻한다. dp배열의 첫 번째 원소 값을 입력받은 수열의 첫 번째 값으로 설정하고, dp배열을 차례대로 업데이트 해주면 된다.

이때 dp[i] = max(dp[i - 1] + arr[i], arr[i])이다. 즉, dp[n]의 값은 dp[n-1]에 arr[n]을 더한 값이나 arr[n] 중 더 큰 값이다. 

dp배열의 특정 원소 값은 이전까지의 연속 부분합에 현재 값을 더하거나, 현재 값부터 새로 시작하는 경우 둘 중 하나이기 때문이다.

코드

n = int(input())

arr = list(map(int, input().split()))

dp = [0] * n # dp[n]의 의미는 n번째 원소를 포함한 연속 부분합 중 최대값을 뜻함.

max_value = max(arr) # 최소 한 개는 골라야 하므로, 시작 값은 arr의 원소들 중 최대값

dp[0] = arr[0] # dp[0]에서의 최대 값은 arr[0] 밖에 없음.

for i in range(1, n):
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
    max_value = max(max_value, dp[i])

print(max_value)