(Python) 백준 1912번 - 연속합

문제 링크: https://www.acmicpc.net/problem/1912

1912번: 연속합

풀이

Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다.

 

문제 해결을 위한 아이디어는 다음과 같다.

1. 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다.
2. 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다.
3. 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다.
4. 최종적으로 최대값들을 담은 배열에서의 최대값이 정답이 된다.

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split(" ")))

_max = [0] * n
_max[0] = arr[0] # 첫번째 인덱스에서의 최대값은 당연히 첫번째 인덱스가 나타내는 값
for i in range(1, n): # 입력값들을 순회하며
    _max[i] = max(arr[i], _max[i-1] + arr[i]) # 현재 인덱스까지의 최대값(현재값 또는 이전까지의 최댓값 + 현재값)을 저장한다.

print(max(_max)) # 모든 인덱스에서의 최댓값 중 최댓값을 출력한다.