[Python_DynamicProgramming] 백준 1912번 : 연속합

코딩문제풀이/Baekjoon

코딩하는 포메라니안 2021. 11. 2. 00:30

1. 문제

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

현재 위치에서 선택할 수 있는 방안은 2가지다.

1) 이전 값에 연속해서 더하기

2) reset하고 현재값부터 다시 시작하기

따라서, 현재값과 연속해서 더한 값 중에 큰 수를 선택해나간다.

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

for i in range(1, len(arr)):
  arr[i] = max(arr[i], arr[i-1]+arr[i])
print(max(arr))