Max Sum Subarray of Size At Least K – Complete Explanation (Java)

Problem Statement

Given an integer array arr[] and an integer k, find the maximum sum of any contiguous subarray whose length is greater than or equal to k.

Example 1

Input

arr = [1, -2, 2, -3]
k = 3

Output

Explanation

Possible subarrays of length at least 3:

Subarray	Sum
[1, -2, 2]	1
[-2, 2, -3]	-3
[1, -2, 2, -3]	-2

Maximum sum = 1

Example 2

Input

arr = [1, 1, 1, 1, 1, 1]
k = 2

Output

The entire array has the maximum sum.

Understanding the Problem

If the question asked for the maximum subarray sum, we could directly use Kadane's Algorithm.

However, there is an additional condition:

The subarray length must be at least k.

Therefore, Kadane's Algorithm alone cannot solve this problem.

Brute Force Approach

Generate every possible subarray having length ≥ k.

Calculate the sum.
Keep track of the maximum sum.

for every starting index
    for every ending index
        if length >= k
             calculate sum

Complexity

Time Complexity

Brute Force: O(n³)
Using Prefix Sum: O(n²)

This is still not efficient because:

n = 100000

We need an O(n) solution.

Optimized Idea

We combine:

Kadane's Algorithm
Sliding Window

Step 1: Kadane's Algorithm

We create an array:

maxEndHere[]

where:

maxEndHere[i]

means:

Maximum subarray sum ending exactly at index i.

Example

Suppose:

Index : 0   1   2   3   4
Value : 2  -3   4   5  -2

i = 0

maxEndHere[0] = 2

i = 1

Either take only:

-3

or extend the previous subarray:

2 + (-3) = -1

Maximum:

-1

maxEndHere[1] = -1

i = 2

Take only:

or extend:

-1 + 4 = 3

Maximum:

maxEndHere[2] = 4

i = 3

Take only:

or extend:

4 + 5 = 9

Maximum:

maxEndHere[3] = 9

i = 4

Take only:

-2

or extend:

9 - 2 = 7

Maximum:

Final array:

maxEndHere = [2, -1, 4, 9, 7]

Code

int[] maxEndHere = new int[n];

maxEndHere[0] = arr[0];

for (int i = 1; i < n; i++) {
    maxEndHere[i] =
        Math.max(arr[i],
                 maxEndHere[i - 1] + arr[i]);
}

Why Do We Need `maxEndHere[]`?

Suppose:

Window size = k

Current window:

[4, 5]

Window sum:

Before this window:

2, -3

There is a positive contribution:

So instead of considering only:

4 + 5

we may use:

2 - 3 + 4 + 5

or simply:

4 + 5

We need whichever is larger.

Kadane's Algorithm already tells us the best prefix ending before the window.

Step 2: Sliding Window

Maintain the sum of exactly k elements.

Example

1 2 3 4 5

k = 3

First window:

1 2 3

sum = 6

Move the window:

Remove:

Add:

New sum:

Move again:

Remove:

Add:

New sum:

This is the Sliding Window technique.

Code

int windowSum = 0;

for (int i = 0; i < k; i++) {
    windowSum += arr[i];
}

Move the window:

windowSum += arr[i];
windowSum -= arr[i - k];

This takes O(1) time instead of recalculating the sum.

Step 3: Why Add `maxEndHere[i - k]`?

Suppose:

arr

2 -1 3 4 5

k = 2

Current window:

4 5

sum = 9

Before the window:

2 -1 3

Maximum subarray ending before the window:

2 -1 +3 = 4

Now extend:

4 + 9 = 13

New subarray:

2 -1 3 4 5

Length:

which is greater than k.

This is why:

windowSum + maxEndHere[i - k]

is checked.

Complete Code

class Solution {

    public int maxSumWithK(int[] arr, int k) {

        int n = arr.length;

        // Step 1: Kadane array
        int[] maxEndHere = new int[n];
        maxEndHere[0] = arr[0];

        for (int i = 1; i < n; i++) {
            maxEndHere[i] = Math.max(arr[i], maxEndHere[i - 1] + arr[i]);
        }

        // Step 2: First window of size k
        int windowSum = 0;

        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int ans = windowSum;

        // Step 3: Slide the window
        for (int i = k; i < n; i++) {

            // Add new element
            windowSum += arr[i];

            // Remove leftmost element
            windowSum -= arr[i - k];

            // Case 1: Exactly k elements
            ans = Math.max(ans, windowSum);

            // Case 2: More than k elements
            ans = Math.max(ans, windowSum + maxEndHere[i - k]);
        }

        return ans;
    }
}

Dry Run

Input

arr = [1, -2, 2, -3]
k = 3

Step 1

Build the Kadane array.

i	arr[i]	maxEndHere[i]
0	1	1
1	-2	max(-2, 1 - 2) = -1
2	2	max(2, -1 + 2) = 2
3	-3	max(-3, 2 - 3) = -1

maxEndHere = [1, -1, 2, -1]

Step 2

First window:

1 -2 2

sum = 1

ans = 1

Step 3

Move the window.

Current window:

-2 2 -3

sum = -3

Exactly k elements:

ans = max(1, -3) = 1

Extend:

windowSum + maxEndHere[0]

-3 + 1 = -2

ans = max(1, -2) = 1

Loop ends.

Return:

Complexity Analysis

Operation	Complexity
Build Kadane array	O(n)
Sliding Window	O(n)
Overall Time	O(n)
Extra Space	O(n)

Key Points to Remember

Kadane's Algorithm computes the maximum subarray sum ending at each index.
Sliding Window efficiently maintains the sum of every subarray of exactly k elements.
For each window, we consider:
- The window itself (length = k).
- Extending it with the best positive subarray ending just before the window (length > k).
The answer is the maximum among all these candidates.

Summary

This approach combines Kadane's Algorithm and the Sliding Window technique to efficiently find the maximum sum subarray whose length is at least k. Kadane's Algorithm precomputes the best subarray ending at every index, while the Sliding Window maintains the sum of every window of size k. Together, they produce the optimal O(n) solution expected in coding interviews and competitive programming.

Problem Statement

Example 1

Example 2

Understanding the Problem

Brute Force Approach

Complexity

Optimized Idea

Step 1: Kadane's Algorithm

Example

i = 0

i = 1

i = 2

i = 3

i = 4

Code

Why Do We Need maxEndHere[]?

Step 2: Sliding Window

Example

Code

Step 3: Why Add maxEndHere[i - k]?

Complete Code

Dry Run

Input

Step 1

Step 2

Step 3

Complexity Analysis

Key Points to Remember

Summary

Why Do We Need `maxEndHere[]`?

Step 3: Why Add `maxEndHere[i - k]`?