Maximum Sum Subarray of Size K

Given an array of integers and an integer k, find the maximum sum of any contiguous subarray of size k.

Example

Input: 2 1 5 1 3 2, k = 3 Output: 9 (the subarray 5 1 3)

Approach

A fixed-size sliding window: compute the sum of the first k elements, then slide right one step at a time — subtract the element leaving the window, add the element entering it. O(n) instead of recomputing each window's sum from scratch.

Input format

Line 1: the array, space-separated Line 2: k