[백준/Python] 1912 연속합

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

 

 

사용 알고리즘: DP

 

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)

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

 

 

n 개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.

(단 수는 한 개 이상 선택해야 함)

-> 부분합을 구하는 문제로 전형적인 dp 문제!

 

만약 dp 로 풀지 않는다면 이중 for 문을 써서 모든 [a, b] 구간합을 다 구해서 확인해야 한다. 이중 for 문을 써서 완전 탐색을 한다면 O(n^2) 의 Big-O 시간을 가지게 되고 문제에서 주어진 n 의 최대 값이 10만 이기 때문에 대략적으로 10억 번의 계산을 하게 된다. 하지만 문제의 제한 시간은 1초이기 때문에 시간 초과가 나게 된다. (컴퓨터는 1초에 약 1억번의 계산을 한다고 생각하면 된다)

 

 

문제에서 수열에서 '연속된' 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려함

-> dp[i] = max(arr[i], dp[i-1] + arr[i])

 

이전까지의 연속된 수를 더한 최대합: dp[i-1] 

다음 차례에 더할 수: arr[i] 

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp = [0] * len(arr)
dp[0] = arr[0]

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

print(max(dp))