[Python] 백준 2559. 수열 (누적합)

누적합 (prefix/cumulative sum)

이 알고리즘은 구간합을 쉽게 구할 수 있도록 하는 알고리즘으로,
각 인덱스 i에 0 ~ i 까지의 누적합을 저장한 배열을 활용한다.
그 배열을 arr라고 할 때, a와 b 인덱스 사이의 구간합을 구한다고 하면 arr[b] - arr[a-1] 하면 된다.

Point

• 수가 음수일 수 있다는 사실..! 그래서 구간합의 최댓값을 업데이트할 때, 최솟값을 양수가 아닌 -10000000으로 설정해야 함

코드

import sys

input = sys.stdin.readline

if __name__ == '__main__':
     n, k = map(int, input().split())
     temp = list(map(int, input().split()))
     dp = [0]
     
     prefix_sum = 0
     for t in temp:
          prefix_sum += t
          dp.append(prefix_sum)
          
     max_sum = -10000000
     for i in range(0, n - k + 1):
          max_sum = max(max_sum, dp[i+k] - dp[i])
     print(max_sum)