Maximum Subarray Sum
Mahabharata — Arjuna's Momentum — The Longest Unbroken Surge of Battle Fortune
यत्र वेगः संचितः तत्र जयः स्वयम्। पूर्वं त्यज यदि भारः — नूतनं आरभस्व॥
*Where momentum accumulates, victory arrives on its own. If the burden of the past weighs you down — begin anew.*
The Story
On the third day of Kurukshetra, Sanjaya was narrating the battle's fortunes to the blind king Dhritarashtra. The day's progress was recorded as a series of numbers — positive for Pandava advances, negative for Pandava losses. The sequence `[-2, 1, -3, 4, -1, 2, 1, -5, 4]` told the story of that day's ebb and flow.
"Which stretch of consecutive battle actions," Dhritarashtra demanded, "gave the Pandavas their maximum cumulative advantage?"
Sanjaya's assistant tried the exhaustive approach: check every possible start and end point, compute each subarray's sum, find the maximum. O(n²) comparisons.
"There are 81 pairs for just 9 positions," the assistant reported. "For the eighteen-day war with thousands of skirmishes..."
"There is a better way," said Vidura, who was present in the chamber. "I learned it from the divine mathematician Kadane, who appeared in a dream. It requires only one pass."
Vidura laid out the insight:
"At each position i, we ask a single question: should the current subarray EXTEND the previous one, or START FRESH at position i?"
"When does starting fresh make sense?" Dhritarashtra asked.
"When the running sum of the previous subarray is NEGATIVE," Vidura said. "If the accumulated momentum is a net liability — if `currSum + nums[i] < nums[i]` — then carrying that baggage into position i only drags us down. It is better to begin at i with just `nums[i]`."
"This simplifies to: `currSum = max(nums[i], currSum + nums[i])`." "Equivalently: if `currSum < 0`, reset to 0 before adding `nums[i]`."
Vidura traced through `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`:
- i=0: currSum = max(-2, 0+(-2)) = -2. maxSum = -2 - i=1: currSum = max(1, -2+1) = max(1,-1) = 1. maxSum = 1 - i=2: currSum = max(-3, 1+(-3)) = max(-3,-2) = -2. maxSum = 1 - i=3: currSum = max(4, -2+4) = max(4,2) = 4. maxSum = 4 - i=4: currSum = max(-1, 4+(-1)) = max(-1,3) = 3. maxSum = 4 - i=5: currSum = max(2, 3+2) = 5. maxSum = 5 - i=6: currSum = max(1, 5+1) = 6. maxSum = 6 - i=7: currSum = max(-5, 6+(-5)) = max(-5,1) = 1. maxSum = 6 - i=8: currSum = max(4, 1+4) = 5. maxSum = 6
"The maximum subarray sum is 6," Vidura announced, "from index 3 to 6: `[4, -1, 2, 1]`."
Dhritarashtra pressed: "But what if ALL values are negative? What if the entire day was a Pandava loss?"
"Then the maximum subarray is the single least-negative element," Vidura said. "The algorithm handles this: we initialize `maxSum = nums[0]`, not `Integer.MIN_VALUE`. If the first element is negative, it becomes the initial maximum. As we proceed, even if all elements are negative, `max(nums[i], currSum+nums[i])` will always choose `nums[i]` when `currSum` becomes sufficiently negative — and `maxSum` tracks the best single element."
Sanjaya delivered the analysis to Dhritarashtra. The three-day battle momentum peaked at a Pandava advantage of 6 — the subarray [4,-1,2,1]. The Kauravas were advised accordingly.
"One pass," Vidura said. "One comparison per element. The choice at each step: carry the momentum forward, or let go and begin again. This is both military wisdom and algorithmic truth."
This is Kadane's Algorithm for finding the maximum subarray sum.
Sanjaya's Assistant's First Instinct
Check every pair of start and end indices. Compute the sum for each subarray. Track the maximum. O(n²) time.
public int maxSubArrayBruteForce(int[] nums) {
int maxSum = Integer.MIN_VALUE;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}Vidura's Wisdom (Kadane's Algorithm)
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; // Best subarray sum seen so far
int currSum = nums[0]; // Best subarray sum ending at current position
for (int i = 1; i < nums.length; i++) {
// Extend previous subarray OR start fresh at i
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
// Equivalent formulation (clearer intent)
public int maxSubArrayAlt(int[] nums) {
int maxSum = nums[0];
int currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (currSum < 0) currSum = 0; // Negative momentum: reset
currSum += nums[i];
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
// Test
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(new Solution().maxSubArray(nums)); // 6 [4,-1,2,1]
int[] allNeg = {-3, -1, -2};
System.out.println(new Solution().maxSubArray(allNeg)); // -1
}Step-by-Step Walkthrough
nums = [5, -3, 5] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=0 (init): currSum=5, maxSum=5 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=1: nums[1]=-3 currSum = max(-3, 5+(-3)) = max(-3, 2) = 2 maxSum = max(5, 2) = 5 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=2: nums[2]=5 currSum = max(5, 2+5) = max(5, 7) = 7 maxSum = max(5, 7) = 7 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return 7 ([5,-3,5] = 7, extending is better than restarting) Verify: [5]=5, [-3]=-3, [5]=5, [5,-3]=2, [-3,5]=2, [5,-3,5]=7 ✓ maximum is 7
Deep Insight
**The core invariant: `currSum` = maximum sum subarray ending exactly at index i**
At each index i, there are exactly two choices: 1. Start a new subarray at i: value = nums[i] 2. Extend the previous subarray: value = currSum + nums[i]
We take the maximum of these two. This is optimal by induction: if the best subarray ending at i-1 has negative sum, including it only hurts; if positive, it helps.
**All-negative arrays:** Initializing with `nums[0]` (not -∞) handles this. As currSum repeatedly resets to single negative elements, maxSum tracks the least-negative one.
**Finding the actual subarray (not just the sum):** Track `start`, `end`, and `tempStart` indices: - When currSum resets (currSum < 0 before adding), set `tempStart = i` - When maxSum updates, set `start = tempStart`, `end = i`
**Kadane's connection to Dynamic Programming:** `maxSumEndingAt[i] = max(nums[i], maxSumEndingAt[i-1] + nums[i])` This is a DP recurrence with O(n) states reduced to O(1) space since we only need the previous state.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All O(n²) start-end pairs checked |
| Optimal | O(n) | O(1) | Single pass, two variables: currSum and maxSum |
Pattern Recognition
✅ Maximum/minimum sum contiguous subarray ✅ Array can contain negative numbers ✅ Single pass with extend-or-reset decision ✅ Classic DP reduced to O(1) space **LeetCode Trigger Phrases:** → "maximum subarray" (the classic) → "contiguous subarray with largest sum" → "can contain negative numbers" + maximize sum
Bhagavad Gita 2.40
नेहाभिक्रमनाशोऽस्ति प्रत्यवायो न विद्यते। स्वल्पमप्यस्य धर्मस्य त्रायते महतो भयात्॥
In this endeavor there is no loss or diminution, and a little advancement on this path can protect one from the most dangerous type of fear.
Connection: Kadane's algorithm never loses accumulated progress — when momentum (currSum) is positive, it carries forward without diminution. When momentum turns negative, it lets go without regret and starts fresh. Like the Gita's teaching that no effort on the path of dharma is ever lost, the algorithm preserves the best sum seen so far in maxSum, even as currSum fluctuates. Progress once made is never truly abandoned.