Java  

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

1

Explanation

Possible subarrays of length at least 3:

SubarraySum
[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

6

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:

4

or extend:

-1 + 4 = 3

Maximum:

4

maxEndHere[2] = 4

i = 3

Take only:

5

or extend:

4 + 5 = 9

Maximum:

9

maxEndHere[3] = 9

i = 4

Take only:

-2

or extend:

9 - 2 = 7

Maximum:

7

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:

9

Before this window:

2, -3

There is a positive contribution:

2

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:

1

Add:

4

New sum:

9

Move again:

Remove:

2

Add:

5

New sum:

12

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:

5

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.

iarr[i]maxEndHere[i]
011
1-2max(-2, 1 - 2) = -1
22max(2, -1 + 2) = 2
3-3max(-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:

1

Complexity Analysis

OperationComplexity
Build Kadane arrayO(n)
Sliding WindowO(n)
Overall TimeO(n)
Extra SpaceO(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.

Membership not found