[백준] 1912 : 연속 합 - Python

연속합

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

import sys
sys.stdin  = open("input.text", "rt")
input = sys.stdin.readline

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

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

#dp에 이제 연속된 수 중 최댓값이 저장되어 있을 것.
#이 중에 최댓값을 구하면 됨.
print(max(dp))

👻 코멘트

이 문제의 핵심은 최대 계산 값을 기록하면서 최대한 빠른 시간 안에 해결해야 한다는 것
즉 현재까지의 연속된 숫자 중 최댓값을 기록해 나가야해.

dp[i]는 i번째 데이터 이전까지 합을 계산했을 때 최댓값을 지속적으로 기록

• dp[i]. 즉 이전까지의 합이 현재 숫자. i번째 숫자보다 작은 경우 이전의 기록들은 필요없어진다 !
• 그러니 그냥 i번째 숫자를 최댓값으로 설정해야지

👻 결국 이 문제의 핵심은 현재 숫자가 음수이면 이 음수를 이전까지의 연속된 합에 더했을 때 0보다 큰지 확인하는 것이 핵심이다. 합했는데 0보다 작은 경우 최댓값으로 이어질 수 없다.

• 이전까지의 합이 음수이면 더할 이유가 없어지잖아 !

i번째까지 연속된 합의 최댓값을 기록해뒀으니 dp의 최댓값이 바로 원하는 값이지.

• 계속 점진적으로 키워나갈 때 어떻게 해결되는지를 생각해야 한다.

첫번째 숫자까지 연속된 숫자합을 dp[1]에 저장하고, 두번째 숫자까지 연속된 숫자합의 최댓값을 dp[2]에 저장하고... 이렇게 하고 싶을때 점화식을 어떻게 해야할까?

• 결국 이전까지의 연속 합이 양수여야 현재 숫자를 더해서 연속 합의 최댓값을 갱신할 수 있다.
• 이걸 알았어야 이 문제를 풀 수 있었음