Maximum Sum Subarray of Size K

Easy·Tagsarraysliding-window

Problem Statement

Given an array of positive numbers and a positive number `k`, find the maximum sum of any contiguous subarray of size `k`.

Examples

Example 1

Input

k: 3, arr: [2, 1, 5, 1, 3, 2]

Output

"9"

Why

Of all the windows of three consecutive elements, [5, 1, 3] has the largest total at 5 + 1 + 3 = 9, so the answer is 9.

Example 2

Input

k: 2, arr: [2, 3, 4, 1, 5]

Output

"7"

Why

Among every pair of consecutive elements, [3, 4] gives the highest sum at 3 + 4 = 7.

Constraints

•1 <= arr.length <= 100000
•1 <= k <= arr.length
•0 <= arr[i] <= 10000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A naive solution would calculate the sum of all 'k' length subarrays, which takes O(N*K) time. Can we do it in O(N)?

Hint 2

Visualize each contiguous subarray as a sliding window of size 'k'.

Hint 3

When moving the window one step forward, we don't need to recalculate the sum from scratch. We can just subtract the element going out of the window and add the element coming into the window.