3207 : 연속된 K개의 합 중 최대2

시간 1.000s · 메모리 256MB · 제출 5 · 정답 4

코드제출 문제 풀기

채점기록 통계 묻고답하기

[3175번 연속된 K개의 합 중 최대의 심화 문제입니다.]

$N$개의 정수 배열에서 연속된 $K$개의 원소 합이 최대가 되는 값을 구하세요.

$N$의 크기가 최대 $100,000$으로 매우 크기 때문에, 각 구간마다 $K$개의 원소를 매번 더하는 2중 반복문($O(N \times K)$) 방식은 시간 초과(TLE)를 받게 됩니다.

이전 윈도우의 맨 앞 원소를 빼고 새로운 원소를 더하는 슬라이딩 윈도우(Sliding Window) 기법이나 누적 합을 활용하여 $O(N)$에 해결하세요.

[제약 조건]
• $1 \le K \le N \le 100000$
• $-10000 \le (\text{각 정수}) \le 10000$
• 입력되는 모든 값은 정수

첫째 줄에 공백으로 구분되어 주어집니다.
둘째 줄에 정수가 공백으로 구분되어 주어집니다.

연속된 원소 합의 최댓값을 출력하세요.

6 3
1 4 2 5 3 6

5+3+6=14