최대 합

면접 대비

시간 제한1초메모리 제한128 MB

요약
n개의 정수와 창 크기 k가 주어질 때, 연속한 k개 항의 합 중 최댓값을 구한다.
난이도

쉬움10점 중 3점

유형
배열, 슬라이딩 윈도우, 누적 합
정답자
아직 제출이 없습니다

문제

정수 nn개로 이루어진 수열 a1,a2,…,ana_1, a_2, \ldots, a_n과 양의 정수 kk (1≤k≤n1 \le k \le n)가 주어진다. 이때 연속한 kk개 항의 합

Si=ai+ai+1+⋯+ai+k−1(1≤i≤n−k+1)S_i = a_i + a_{i+1} + \cdots + a_{i+k-1} \quad (1 \le i \le n-k+1)

의 최댓값을 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 양의 정수 nn (1≤n≤1000001 \le n \le 100000)과 양의 정수 kk (1≤k≤n1 \le k \le n)가 공백을 사이에 두고 순서대로 주어진다. 둘째 줄부터 1+i1 + i번째 줄 (1≤i≤n1 \le i \le n)에는 수열의 ii번째 항 aia_i (−10000≤ai≤10000-10000 \le a_i \le 10000)가 한 줄에 하나씩 주어진다.

출력

한 줄에 SiS_i의 최댓값만을 출력한다.

예제1

  1. 예제 1

    입력
    5 3
    2
    5
    -4
    10
    3
    
    예상 출력
    11