[백준] [Python] 1912번_연속합_동적 프로그래밍

문제

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

1912번: 연속합

풀이

# 백준 1912번 문제 - 연속합
n = int(input())
arr =list(map(int, input().split()))

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

print(max(d))

이번 문제는 배열이 주어지면 순서대로 합하여 최댓값을 구하는 문제였다.

이 문제에서는 동적 프로그래밍을 사용하기 위해 점화식을 찾으려고 애썻지만 잘 생각이 나지 않았다.

일단 먼저 내가 생각했던 것은 처음 배열 부터 순차대로 더하여 모든 값을 d에 저장하고 max를 사용하여 값을 구하려고 했으나 코드로 구현하지 못하였다. 

조금 더 생각해본 결과 모든 값을 비교할 필요가 없었다.