새싹프로그래머의 이야기

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

문제: 임의의 수열에서 몇 개의 수를 선택하여 구할 수 있는 수 중  가장 큰 값을 구하는 문제 입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [0] * n

dp[0] = array[0]

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

print(max(dp))

임의의 몇개를 구해서 최대가 되는 값을 구하는 문제 이므로, 이전까지의 연속 합 + 현재 값  / 현재 값을 비교해서 더 큰 값을 dp에 저장해 줍니다.

<문제 예시> 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 를 들어 설명해보겠습니다.

10 -4 3 1 5 6을 거치면서

dp = [10,6,9,10,15,21]이 저장됩니다.

이후 -35를 만나게 되면

dp[6]에는 -14가 저장되게 됩니다.

여기에서 저 연산이 빛을 발휘하게 됩니다.

12을 만났을 경우, dp[7]에는 -14 + 12 = -2가 아닌 12가 저장되게 됩니다.

즉, 이전까지 선택된 연속된 값이 현재 값보다 작으므로 12부터 다시 선택하게 되는 효과를 발휘하는 것입니다.

최종 dp에는 [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] 값이 담겨서 

제일 큰 값을 출력해주게 되면 선택할 수 있는 연속된 수 중 제일 큰 합을 구할 수 있습니다.