시간복잡도 줄이는 기술 1. prefix(1)

문제

n개의 원소로 이루어진 수열이 주어졌을 때, 이 중 연속하는 k개의 원소들의 합 중 가장 큰 값을 구하는 프로그램

아이디어 - prefix sum? 

prefix sum 배열 : 처음부터 각 위치까지의 숫자를 전부 더한 배열

무작정 for 문을 돈다면 구간마다 숫자들을 전부 순회해야하는데

구간의 최대 크기가 N이고 질의의 개수가 Q일 때 , 총 시간복잡도 O(QN) -> prefix 사용시 O(1)

 

 

누적합을 이용할 때 1~n까지 인덱스를 사용한다면, 0번째 인덱스에 꼭 값 0을 넣어야함

 

코드

import sys

n,k=map(int,sys.stdin.readline().split())
arr=[0]+list(map(int,sys.stdin.readline().split()))
prefix_sum = [0]*(n+1) 

def get_sum(s, e):
    return prefix_sum[e] - prefix_sum[s - 1]

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

ans=0
for i in range(1, n-k + 2 ) : #+2 -> 1. 앞에 [0]을 더해서 idx+1 /  2.idx 계산할 때 i+k-1이기에 마지막 원소 포함하려면 +1

    ans = max(ans, get_sum(i, i + k - 1))
print(ans)