2022-08-23 @이영훈
접근방법
전형적인 Dynamic Programming 문제입니다. 문제에 주어진 시간이 1초인 점과 memoization하는 변수가 없으면 계산량이 많은 점을 통해 생각할 수 있습니다.
total이라는 memoization을 위한 변수를 선언합니다.
total은 직전의 수(total[i - 1])가 양수이면 현재의 수와 더했을 때 수가 더 커지기 때문에 더합니다.
total[i] = numbers[i] + total[i - 1]
그렇지 않고 직전의 수가 0이거나 음수이면 현재의 수가 가장 큰 수이기 때문에 현재의 수를 더합니다
total[i] = numbers[i]
이렇게 만들어진 total 변수에서 최대값이 정답입니다.
파이썬 코드
import sys
input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))
total = [0] * n
total[0] = numbers[0]
for i in range(1, n):
if total[i - 1] > 0:
total[i] = numbers[i] + total[i - 1]
else:
total[i] = numbers[i]
print(max(total))
Python
복사