[BAEKJOON] 1912_연속합_Python

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

1912번: 연속합

 

문제

 

 

문제 해설

(1) N개의 수로 이루어진 수열이 주어진다.
(2) 이중, 연속된 수를 임의로 선택하여 만들 수 있는 최대 합을 구하는 문제이다.

 

 

문제 풀이

dp를 활용하면 된다.

연속된 숫자의 합을 구하는 문제이기에, 현재 지점을 기준으로 앞에 위치한 값들에 대해서만 최댓값을 갱신해주면 연속성과 최댓값이 유지된다.
그래서 dp에는 자신의 앞에 위치한 수까지의 최대 연속합 + 현재값과  현재값 중 큰 값을 저장하면 된다.
dp[i] = max(dp[i - 1] + arr[i], arr[i])

 

 

* 코드

from sys import stdin

n = int(stdin.readline())
arr = list(map(int, stdin.readline().rstrip().split()))
summed = arr[:]
answer = [0 for _ in range(len(arr))]

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

print(max(summed))