Max Sum Subarray of Size at least K

Time: O(n)

Space: O(n)

Problem Overview

Find the maximum sum among contiguous subarrays whose length is at least k.

Intuition

Find the maximum sum among contiguous subarrays whose length is at least k. Every candidate ending at i must include the last k elements ending at i. Prefill Kadane best-ending sums, then slide a window of size k and optionally glue on the best sum that ends just before the window when that helps.

Algorithm

1Build maxSum[i] = maximum subarray sum ending at i via Kadane.
2sum = arr[0..k-1]; ans = sum.
3For i = k..n-1: slide sum by +arr[i] - arr[i-k]; ans = max(ans, sum, sum + maxSum[i-k]).
4Return ans.

Example Walkthrough

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

1. Exact windows of length 2: [1,-2]=-1, [-2,2]=0, [2,-3]=-1.
2. Extend with Kadane prefixes where helpful: [1,-2,2] sums to 1.
3. Best among length >= 2 is 1.

Output: 1

Common Pitfalls

• Plain Kadane alone is wrong - it can return a subarray shorter than k.
• Always compare both exact-k window and window plus maxSum[i-k].
• If maxSum[i-k] is negative, the exact-k candidate wins automatically.
• Array length is guaranteed >= k; still initialize ans from the first window.

Max Sum Subarray of Size at least K.java

Java

// Approach: Any max-sum subarray of length >= k ending at i must keep the last
// k elements ending at i. Prefill maxSum[j] = best Kadane sum ending at j, then
// slide a fixed window of size k. At each right end i, answer is max(window,
// window + maxSum[i-k]) so length can grow only when the best prefix helps.
// Time: O(n) Space: O(n)
class Solution {

    public int maxSumWithK(int[] arr, int k) {
        int n = arr.length;
        // maxSum[i] stores maximum subarray sum ending at index i
        int[] maxSum = new int[n];
        maxSum[0] = arr[0];
        int curr = arr[0];
        for (int i = 1; i < n; i++) {
            curr = Math.max(arr[i], curr + arr[i]);
            maxSum[i] = curr;
        }
        // Sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }
        int ans = sum;
        // Extend window
        for (int i = k; i < n; i++) {
            sum += arr[i] - arr[i - k];
            // Window of exactly k
            ans = Math.max(ans, sum);
            // Window of size > k
            ans = Math.max(ans, sum + maxSum[i - k]);
        }

        return ans;
    }
}

Was this solution helpful?