[python/파이썬] 백준 1912 연속합

문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

[문제 풀이]

 

임의의 수열이 주어졌을 때 이 수열에서 연속하는 값들을 더했을 때의 가장 큰 값을 구하는 문제이다.

하나 이상의 값을 더해야 한다.

 

연속하는 값들을 더하는 경우는 여러가지가 존재할 것이다.

 

하나의 값만 선택할 수도 있을 것이고, 두 개 이상의 값을 선택하여 더할 수도 있다.

 

코드는 수열을 순회하면서 dp값을 채운다.

수열의 첫번째값을 기본으로 리스트에 저장하고

그 값과 다음값을 더한 경우가 첫 번째 값만 선택했을 때보다 더 크다면 그 값을 dp에 저장한다.

그러면 dp[1] = numbers[0]+numbers[1] 이 될 것이다.

 

이런 식으로 반복하다 보면 앞에서 누적해서 더해온 값보다 현재 수열의 값이 더 크다면 

현재 값부터 다시 더하게 된다.

 

문제에서 제시한 예시를 살펴보면

 

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 

이라는 수열이 존재할 때

 

numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

dp = [10]

인 상태로 for문을 시작하게 된다.

 

i=1부터 시작한다

dp[0] = 10

 

i=1

numbers[1] = -4 > dp[0]+numbers[1] = 10 - 4 = 6

dp = [10, 6]

 

i=2

numbers[2] = 3 < dp[1]+numbers[2] = 6+3 = 9

dp = [10, 6, 9]

 

i=3

numbers[3] = 1 < dp[2]+numbers[3] = 9+1 = 10

dp = [10, 6, 9, 10]

 

i=4

numbers[4] = 5 < dp[3]+numbers[4] = 10 + 5 = 15

dp = [10, 6, 9, 10, 15]

 

i=5

numbers[5] = 6 < dp[4]+numbers[5] = 15 + 6 = 21

dp = [10, 6, 9, 10, 15, 21]

 

i=6

numbers[6] = -35 < dp[5]+numbers[6] = 21 + (-35) = -14

dp = [10, 6, 9, 10, 15, 21, -14]

 

i=7

numbers[6] = 12 > dp[6]+numbers[7] = (-14) + 12 = -2

dp = [10, 6, 9, 10, 15, 21, -14, 12]

 

i=8

numbers[6] = 21 < dp[7]+numbers[8] = 12 + 21 = 33

dp = [10, 6, 9, 10, 15, 21, -14, 12, 33]

 

i=9

numbers[6] = -1 < dp[8]+numbers[9] = 33 + (-1) = 32

dp = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

 

max => 33

 

[소스 코드]

 

import sys

input = sys.stdin.readline

n = int(input())

numbers = list(map(int, input().split()))

dp  = []
dp.append(numbers[0])

for i in range(1,len(numbers)):
    dp.append(max(numbers[i], dp[i-1]+numbers[i]))

print(max(dp))