Maximum Sum Subarray of Size K — Problem & Solution
Maximum Sum Subarray of Size K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Sum Subarray of Size K is an easy coding problem on arrays and sliding window, asked in Amazon, Microsoft and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Sliding Window
- Asked at: Amazon, Microsoft, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array arr and a positive integer k (with k <= arr.length), return the maximum sum of any contiguous subarray of exactly k elements.
Example 1
Input: arr = [100,200,300,400], k = 2
Output: 700
Explanation: The last two elements give the best pair.
Example 2
Input: arr = [1,4,2,10,23,3,1,0,20], k = 4
Output: 39
Explanation: [4,2,10,23] sums to 39.
Example 3
Input: arr = [-1,-2,-3], k = 2
Output: -3
Explanation: Even all-negative input has a best window.
Constraints
1 <= k <= arr.length <= 100000-10000 <= arr[i] <= 10000
Hints for Maximum Sum Subarray of Size K
Hint 1
Recomputing each window from scratch is
O(n · k)— most of the work repeats.Hint 2
Two neighbouring windows differ by one element entering and one leaving.
Hint 3
Seed the sum with the first
kelements, then roll it forward.
How to solve Maximum Sum Subarray of Size K
The canonical fixed-size window. Compute the first window's sum once, then slide: add the element entering on the right and subtract the one leaving on the left.
Approach
- Sum
arr[0 … k-1]and record it as the best. - For each
ifromkonwards, dosum += arr[i] - arr[i - k]. - Keep the maximum seen.
Why it works
Window [i-k+1, i] and window [i-k, i-1] share k-1 elements, so their sums differ by exactly the two boundary elements. Updating in constant time makes the whole scan linear instead of quadratic.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Initialising the best to
0breaks on all-negative input — seed it with the first window. - The roll must both add and subtract; forgetting the subtraction turns it into a prefix sum.
- Sums reach
10^5 · 10^4 = 10^9, which fitsintwith little room to spare.
Reference solution
Python
from typing import List
def maximumSumSubarray(arr: List[int], k: int) -> int:
total = sum(arr[:k])
best = total
for i in range(k, len(arr)):
total += arr[i] - arr[i - k]
best = max(best, total)
return bestJava
public static int maximumSumSubarray(int[] arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int best = sum;
for (int i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k];
best = Math.max(best, sum);
}
return best;
}C++
int maximumSumSubarray(vector<int>& arr, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int best = sum;
for (int i = k; i < (int) arr.size(); i++) {
sum += arr[i] - arr[i - k];
best = max(best, sum);
}
return best;
}JavaScript
var maximumSumSubarray = function(arr, k) {
var sum = 0;
for (var i = 0; i < k; i++) sum += arr[i];
var best = sum;
for (var j = k; j < arr.length; j++) {
sum += arr[j] - arr[j - k];
if (sum > best) best = sum;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sliding Window Technique