[Python][백준] 1912_연속합

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

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보다 작거나 같은 정수이다.

 

출력

첫째 줄에 답을 출력한다.

---

 

동적계획법(DP)으로 점화식만 만들어내면 구현은 아주 쉬운 문제인데, 그 아이디어를 찾는게 참 쉽지 않다.

 

 

p[n]을 n번까지 숫자가 주어질 때 n번 째 숫자를 선택하여 얻을 수 있는 최대 연속합이라고 하자.

p[n]은 num[x]~num[n]까지의 연속합 (x <= n) 중 최대값이다.

이는 p[n-1] (~n-1까지의 연속합)에 num[n]을 더해준 값과 같은데, 단!! p[n-1] + num[n] < num[n] 이라면 이전 값들과의 연속값을 구하는 것 보다 n번째 자리부터 연속값을 구해나가는 것이 더 이득이다.

 

즉 => p[n] = max(p[n-1]+num[n], num[n]) 이다.

 

쉽게 설명하자면, n번째에서 누적합이 음수가 되면! 구간의 시작점을 n+!로 바꾸어 p배열을 구하여 그 중 최대값을 찾는 문제이다.

 

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().strip().split()))

p = [ 0 for _ in range(N)]
p[0] = num[0]

for r in range(1,N):
    p[r] = max(p[r-1]+num[r], num[r])

print(sorted(p)[N-1])

 

머리야 좀 똑똑해져라..