BOJ 1912 연속합

문제

접근 방법

가능한 구간의 길이마다 모든 경우의 수를 직접 구하기( O(n*n) )에는 시간 초과가 난다.

dp를 통해서 dp[i]에는 i번째 위치까지의 제일 큰 부분합을 저장하면 된다.

정답 코드

import sys
input = sys.stdin.readline


"""
가능한 구간의 길이마다 모든 경우의 수를 직접 구하기( O(n*n) )에는 시간 초과가 난다.

dp를 통해서 dp[i]에는 i번째 위치까지의 제일 큰 부분합을 저장하면 된다.
"""

n = int(input())

nums = list(map(int, input().split()))
dp = [-int(1e9)]*(n+1)

for i in range(n):
  dp[i] = nums[i]

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

print(max(dp))