[알고리즘/백준] 1912번 - 연속합

카테고리 : DP(다이나믹 프로그래밍) 

1912번 연속합 - https://www.acmicpc.net/problem/1912

 

예제 입력 1 

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

예제 출력 1 

33

---

접근 방법

 

n개의 정수로 이루어진 임의의 수열 중 연속된 수들의 합이 가장 큰 경우를 출력해야 한다.

특정 수의 경우의 수는 이전에 연속된 합을 선택하거나 선택하지 않는 경우이다.
선택하는 경우 : 이전 합에 자신의 수를 더한 값
선택하지 않는 경우 : 자신의 수 (이전에 연속된 합을 선택하지 않으면서 현재 숫자가 처음이 된다)

처음에는 더한 모든 경우의 수를 배열에 저장해야 할까 생각했는데 과정을 적어보니 결국 이전 값이 가장 큰 경우에 자신의 수를 더하는 경우가 합이 가장 클 수 밖에 없다. 따라서 그 값만 계속 저장하는 식으로 풀이를 작성했다.

 

dp = max(dp + num[i], num[i])

그리고 answer이라는 변수를 따로 둠으로써 각 숫자의 차례까지의 연속합 중 가장 큰 경우를 저장한다.
이렇게 하지 않으면 문제 예제의 1번의 경우 12 + 21에 마지막 숫자의 -1이 더해진 값 32가 가장 큰 경우로 출력하게 된다.

---

최종 제출 코드

N = int(input())
num = list(map(int, input().split()))

answer = num[0]
dp = num[0]
for i in range(1, len(num)):
    dp = max(dp + num[i], num[i])
    answer = max(dp, answer)