[BOJ][python] 1912. 연속합

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

1912번: 연속합

---

💡IDEA

동적계획법을 사용하는 문제이다.

처음 값부터 연속해서 합을 구하는데, 이전까지 연속합에 현재 값을 더한 것과 그냥 현재 값을 비교하여 큰 값을 dp 배열에 저장한다.

이렇게 되면 연속하는 수 중에서 가장 큰 합을 구할 수 있다.

예를 들어, n = 10, numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 인 경우를 생각해보자.

dp 배열은 5번째 인덱스까지 [10, 6, 9, 10, 15, 21] 식으로 순조롭게 진행되지만, 6번째 인덱스에서 -35를 만나면서 [10, 6, 9, 10, 15, 21, -11]이 되고, 7번째 인덱스에서 연속합으로 구한 -11보다 그냥 현재 값인 12을 가져오는 것이 큰 값이다. 마지막까지 진행한다면 dp = [10, 6, 9, 10, 15, 21, -11, 12, 33, 32]가 되면서, 이 중 가장 큰 값인 33을 출력한다.

 

📌CODE

import sys
input = sys.stdin.readline

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

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

print(max(dp))