Maximum Sum Subarray of Size K

Easy
779.

Maximum Sum Subarray of Size K

Maximum Sum Subarray of Size K is an easy coding problem on arrays and sliding window, asked in Amazon, Microsoft and TCS interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maximumSumSubarray = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Recomputing each window from scratch is O(n · k) — most of the work repeats.

  2. Hint 2

    Two neighbouring windows differ by one element entering and one leaving.

  3. Hint 3

    Seed the sum with the first k elements, 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

  1. Sum arr[0 … k-1] and record it as the best.
  2. For each i from k onwards, do sum += arr[i] - arr[i - k].
  3. 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 0 breaks 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 fits int with 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 best

Java

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