Maximum Sum Subarray of Size K
Ramayana — Sugriva's Scout Patrol — The Window of K Warriors Sweeping Lanka's Shore
खातं त्यजति पूर्वं नवं ग्रहणं कुरु। सर्वेषां योगे श्रेष्ठं K-दलस्य बलम् ज्ञेयम्॥
*Release the old as you receive the new. The maximum strength lies in the optimal group of K.*
The Story
When Sugriva, king of the Vanaras, agreed to help Rama find Sita, he faced a reconnaissance challenge that would determine the efficiency of the entire search mission.
Lanka's northern shore was divided into n sectors, each with a known warrior density — a number representing how many enemy soldiers patrolled that sector. Sugriva needed to send a patrol unit of exactly K Vanara warriors to scout a contiguous block of K sectors. To maximize intelligence gathering, the patrol should be sent to the K sectors with the highest combined enemy density — where the intelligence would be richest.
"We need to find the K contiguous sectors with the maximum total warrior density," Sugriva's general Nila reported.
Angada, Sugriva's young nephew who was always eager to prove himself, suggested the direct approach: "General, for every possible starting sector, let me sum up the K sectors starting from there. Compare all those sums and take the maximum."
"How many starting positions would you check?" Nila asked.
"n - K + 1 positions. For each, K additions. About n×K total operations," Angada calculated.
"For a coast with 10,000 sectors and a patrol of 1,000 warriors," Nila said, "that is 10 million operations."
"There is a better way," said Hanuman, who had already scouted Lanka personally and understood efficiency deeply. "Watch."
Hanuman took Angada's sector-density chart: `[2, 1, 5, 1, 3, 2]` with K = 3.
"First, compute the sum of the first K sectors: 2+1+5 = 8. This is our initial window sum."
"Now, to slide the window one sector to the right: we don't recompute from scratch! We REMOVE the leftmost sector of the current window (sector 0, value 2) and ADD the new rightmost sector (sector 3, value 1). New sum = 8 - 2 + 1 = 7."
"Slide again: remove sector 1 (value 1), add sector 4 (value 3). New sum = 7 - 1 + 3 = 9."
"Slide again: remove sector 2 (value 5), add sector 5 (value 2). New sum = 9 - 5 + 2 = 6."
"Maximum window sum = 9, achieved by sectors [2,3,4] with values [5,1,3]."
Angada stared. "Each slide requires just two operations — one subtraction, one addition — instead of K additions!"
"Exactly," Hanuman nodded. "We slide a window of fixed size K across the array. The window always contains exactly K elements. When we move right, we drop the leftmost element and gain a new rightmost element. We maintain a running sum that updates in O(1) per slide."
"The key insight," Hanuman continued, "is that consecutive windows overlap in K-1 elements. Recomputing from scratch throws away that overlap. The sliding window preserves it."
"Why is this possible?" Angada asked.
"Because the window size is fixed," Hanuman replied. "A fixed window size means we always know exactly what to add (new right element) and what to remove (old left element). The window's left and right boundaries move in lockstep — right boundary is always left boundary + K."
Nila pointed to the chart: "The patrol of K=3 goes to sectors [2,3,4] — the valley, the ridge, and the slope — with density 5+1+3=9. Maximum intelligence coverage with minimum warrior displacement."
Sugriva dispatched the patrol. Their reconnaissance of the densest K-sector corridor revealed Ravana's primary defensive formation — intelligence that would prove critical in the final battle.
"Remember," Hanuman told Angada as the patrol departed, "whenever the problem asks for a maximum or minimum property of a FIXED-SIZE window, slide it. Don't recompute. Drop the old, add the new, track the maximum."
This is the Sliding Window technique for finding the maximum sum subarray of size K.
Angada's First Instinct
For each starting index, compute the sum of K elements from scratch. Compare with the running maximum. O(n×K) time — recomputes overlapping regions repeatedly.
public static int maxSumBruteForce(int[] arr, int k) {
int n = arr.length;
int maxSum = Integer.MIN_VALUE;
// Try every starting position
for (int i = 0; i <= n - k; i++) {
int windowSum = 0;
// Sum the k elements starting at i
for (int j = i; j < i + k; j++) {
windowSum += arr[j];
}
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Hanuman's Wisdom
public static int maxSum(int[] arr, int k) {
int n = arr.length;
if (n < k) return -1; // Not enough elements
// Build the first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum; // First window is initial maximum
// Slide the window across the array
for (int i = k; i < n; i++) {
// Add new right element, remove old left element
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Test with Lanka's sector densities
public static void main(String[] args) {
int[] sectors = {2, 1, 5, 1, 3, 2};
int k = 3;
System.out.println(maxSum(sectors, k)); // 9 (subarray [5,1,3])
int[] sectors2 = {2, 3, 4, 1, 5};
System.out.println(maxSum(sectors2, 2)); // 7 (subarray [3,4])
}Step-by-Step Walkthrough
arr = [2, 1, 5, 1, 3, 2], k = 3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ INITIALIZATION — first window [0..2] windowSum = arr[0]+arr[1]+arr[2] = 2+1+5 = 8 maxSum = 8 Window: [2, 1, 5] | 1, 3, 2 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=3: add arr[3]=1, remove arr[0]=2 windowSum = 8 + 1 - 2 = 7 maxSum = max(8, 7) = 8 Window: 2 | [1, 5, 1] | 3, 2 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=4: add arr[4]=3, remove arr[1]=1 windowSum = 7 + 3 - 1 = 9 maxSum = max(8, 9) = 9 ← NEW MAXIMUM Window: 2, 1 | [5, 1, 3] | 2 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=5: add arr[5]=2, remove arr[2]=5 windowSum = 9 + 2 - 5 = 6 maxSum = max(9, 6) = 9 Window: 2, 1, 5 | [1, 3, 2] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return maxSum = 9 Best window: [5, 1, 3] at indices [2, 3, 4]
Deep Insight
**Why is the sliding window 2 operations instead of K?**
The key observation: `sum(arr[i..i+k-1]) = sum(arr[i-1..i+k-2]) - arr[i-1] + arr[i+k-1]`. Each slide is exactly 1 subtraction + 1 addition, regardless of K. This is the power of the recurrence relation in the sliding window.
**Fixed window vs Variable window:** This problem has a FIXED window size K. Fixed windows use `i - k` as the left boundary (exact). Variable-size windows (used when optimizing for sum ≤ target or other conditions) need explicit left pointer management.
**Edge cases:** - K > n: impossible, return -1 or handle per problem spec - K == n: the only window is the entire array - K == 1: maximum of individual elements - All negative: sliding window still works (picks the "least negative" window)
**When to recognize this pattern:** - Fixed window size K stated in problem - "Maximum/minimum sum of exactly K elements" - Any aggregation (sum, average, count) over a fixed-size window
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × k) | O(1) | For n=10,000 sectors and k=1,000: 10 million additions |
| Optimal | O(n) | O(1) | Single pass, 2 operations per window slide regardless of k |
Pattern Recognition
✅ Contiguous subarray of exactly size K ✅ Maximize (or minimize) sum/average over a fixed window ✅ O(n) single-pass solution possible ✅ Fixed window size makes it easy to identify the 'drop' element **LeetCode Trigger Phrases:** → "maximum sum of subarray of size k" → "maximum average subarray of length k" → "contiguous subarray" + "exactly k elements"
Bhagavad Gita 3.8
नियतं कुरु कर्म त्वं कर्म ज्यायो ह्यकर्मणः। शरीरयात्रापि च ते न प्रसिद्ध्येदकर्मणः॥
Perform your prescribed duty, for action is better than inaction. Even the maintenance of your body would not be possible through inaction.
Connection: The sliding window technique embodies the Gita's principle of prescribed action — doing exactly what needs to be done, no more, no less. As the window slides, it performs only two operations (add new, remove old) instead of the wasteful K operations of brute force. Like dharmic action that is precisely calibrated — not zero (inaction, which fails) and not excessive (recomputing the whole sum, which wastes) — the sliding window acts minimally and achieves maximum efficiency.