Maximum Sum Subarray of Size K

Commonly asked at:Amazon

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

Not solved yet

Ctrl+Enter

Editor

nums = list(map(int, input().split()))
k = int(input())
# TODO: fixed-size sliding window
window_sum = sum(nums[:k])
best = window_sum

nums = list(map(int, input().split()))
k = int(input())
# TODO: fixed-size sliding window
window_sum = sum(nums[:k])
best = window_sum

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

nums = list(map(int, input().split()))
k = int(input())
# TODO: fixed-size sliding window
window_sum = sum(nums[:k])
best = window_sum

nums = list(map(int, input().split()))
k = int(input())
# TODO: fixed-size sliding window
window_sum = sum(nums[:k])
best = window_sum

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.

Loading…