백준 1912번 "연속합"

문제

백준 1912번 연속합

풀이

dp 배열의 첫 인덱스에 arr[0]을 넣어 비교할 수 있도록 하고,
dp[i-1] + arr[i]과 arr[i] 중 최대값을 dp[i]에 넣는 것을 반복한다.

답은 dp배열의 최댓값에 해당한다.

Python 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [0]*n
dp[0] = arr[0]

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

print(max(dp))