[백준/Python3] 연속합

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

---

풀이

수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 값 중 최대값을 구하는 문제다. dynamic programming 을 이용해 간단히 해결할 수 있다.

dp[i]는 i까지의 수열 중 연속한 수의 최대 값이 들어있다. 만약 연속한 수의 최대 값 + i번째 수가 i번째 값보다 작을 경우 dp[i] == arr[i]이다. 이 경우 i번째 수가 이전까지의 연속한 최댓값을 더한 것보다 크다는 의미이므로 i번째 수로 다시 연속을 시작하는게 더 이득임을 알 수 있다.

따라서, 연속한 수의 최대값을 구하는 식은 다음과 같다.

for i in range(1, n):
    if arr[i] <= arr[i] + dp[i-1]:
        dp[i] = arr[i] + dp[i-1]
    else:
        dp[i] = arr[i]

코드

import sys
input = sys.stdin.readline

# Initial
answer = 0
n = int(input())
arr = list(map(int, input().split()))

# Make dp table
dp = [0 for _ in range(n)]
dp[0] = arr[0]
for i in range(1, n):
    if arr[i] <= arr[i] + dp[i-1]:
        dp[i] = arr[i] + dp[i-1]
    else:
        dp[i] = arr[i]

# Answer
answer = max(dp)
print(answer)