Maximum Product Subarray
Mahabharata — Shakuni's Dice — How Negative Fortune Can Multiply Into Maximum Gain
ऋणं ऋणेन गुणितं धनं भवति। धनं ऋणेन गुणितं ऋणं भवति — सावधानं चलेत्॥
*Negative multiplied by negative becomes positive. Positive multiplied by negative becomes negative — walk carefully.*
The Story
Shakuni's dice were enchanted with a peculiar property: some faces showed positive multipliers, others showed negative ones. The game proceeded through n rolls, each roll multiplying the running score. Shakuni had arranged a specific sequence: `[2, 3, -2, 4]`.
Karna, watching the game, posed a question to the court mathematician: "What is the maximum product achievable from any contiguous sequence of these dice rolls?"
The mathematician's first attempt was to adapt Kadane's algorithm directly. "We track `maxProduct` at each step," he said. But immediately ran into trouble: `[2, 3, -2, 4]`. At `-2`, the running max becomes negative. At `4`, multiplying `-6 × 4 = -24` — terrible. But starting fresh gives `4`. Answer: 6 (the subarray `[2,3]`).
But then Shakuni revealed a twist: `[-2, 3, -4]`. - Following just maxProduct: `max(-2, 1×-2)=-2`. `max(3,-2×3)=max(3,-6)=3`. `max(-4,3×-4)=max(-4,-12)=-4`. Answer: 3. - But the actual answer is 24! `[-2 × 3 × -4] = 24`. Two negatives make a massive positive!
"The problem," the mathematician realized, "is that a very negative product can FLIP to a very positive product when multiplied by another negative number. We must track BOTH the maximum AND minimum product ending at each position."
Vidura stepped in: "At each position i, maintain two values:" - `maxProd`: the maximum product of any subarray ending at i - `minProd`: the minimum product of any subarray ending at i (most negative — could become most positive)
"When we encounter a new element `nums[i]`, three candidates exist for the new max:" 1. `nums[i]` itself (start fresh) 2. `maxProd × nums[i]` (extend the current max subarray) 3. `minProd × nums[i]` (the minimum product flips sign if nums[i] < 0!)
"The new max = max(nums[i], maxProd×nums[i], minProd×nums[i])" "The new min = min(nums[i], maxProd×nums[i], minProd×nums[i])"
"But we must be careful: we compute new max and new min SIMULTANEOUSLY from the OLD values. If we update maxProd first, it corrupts the computation of new minProd."
"The shortcut," Vidura continued, "is: if `nums[i] < 0`, SWAP `maxProd` and `minProd` before multiplying. A negative number flips the relationship — what was maximum becomes minimum and vice versa."
Vidura traced through `[-2, 3, -4]`: - i=0: maxP=-2, minP=-2, res=-2 - i=1 (3 > 0, no swap): newMax=max(3,-2×3,-2×3)=max(3,-6,-6)=3. newMin=min(...)=-6. res=3 - i=2 (-4 < 0, SWAP maxP↔minP first): maxP=-6, minP=3. newMax=max(-4,-6×-4,3×-4)=max(-4,24,-12)=24. res=24!
"The maximum product is 24 — the entire array `[-2,3,-4]`," Vidura confirmed.
Shakuni had miscalculated. The negative values in his sequence, which he thought would protect his arrangement, had combined to produce a massive positive product for the Pandavas.
"Two negatives make a positive," Shakuni muttered. "And tracking both extremes reveals the maximum," Vidura replied.
This is Kadane's Algorithm adapted for maximum product subarray.
The Mathematician's First Instinct
Try every subarray. Compute the product (avoid zero division). Track the maximum product. O(n²) time.
public int maxProductBruteForce(int[] nums) {
int maxProd = Integer.MIN_VALUE;
for (int start = 0; start < nums.length; start++) {
int product = 1;
for (int end = start; end < nums.length; end++) {
product *= nums[end];
maxProd = Math.max(maxProd, product);
}
}
return maxProd;
}Vidura's Wisdom — Track Both Extremes
public int maxProduct(int[] nums) {
int maxP = nums[0]; // Max product ending at current position
int minP = nums[0]; // Min product ending at current position (could flip!)
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
// If current number is negative, swap max and min
// (multiplying by negative flips which is larger)
if (nums[i] < 0) {
int temp = maxP;
maxP = minP;
minP = temp;
}
// Extend or start fresh
maxP = Math.max(nums[i], maxP * nums[i]);
minP = Math.min(nums[i], minP * nums[i]);
result = Math.max(result, maxP);
}
return result;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().maxProduct(new int[]{2, 3, -2, 4})); // 6
System.out.println(new Solution().maxProduct(new int[]{-2, 3, -4})); // 24
System.out.println(new Solution().maxProduct(new int[]{0, 2})); // 2
System.out.println(new Solution().maxProduct(new int[]{-2, 0, -1})); // 0
}Step-by-Step Walkthrough
nums = [2, 3, -2, 4] ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=0 (init): maxP=2, minP=2, res=2 i=1 (nums=3, positive, no swap): maxP = max(3, 2×3) = max(3,6) = 6 minP = min(3, 2×3) = min(3,6) = 3 res = max(2, 6) = 6 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=2 (nums=-2, NEGATIVE → SWAP maxP↔minP): maxP was 6, minP was 3 → now maxP=3, minP=6 maxP = max(-2, 3×(-2)) = max(-2,-6) = -2 minP = min(-2, 6×(-2)) = min(-2,-12) = -12 res = max(6, -2) = 6 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ i=3 (nums=4, positive, no swap): maxP = max(4, -2×4) = max(4,-8) = 4 minP = min(4, -12×4) = min(4,-48) = -48 res = max(6, 4) = 6 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return 6 (subarray [2,3])
Deep Insight
**Why product is harder than sum:** For sums: negative values reduce the sum → reset when negative For products: a large negative × another negative = large positive. We can't simply reset on negative — we might lose a future flip opportunity.
**The zero case:** If `nums[i] = 0`, both `maxP × 0 = 0` and `nums[i] = 0`. So maxP = min(0, 0) = 0. Both reset to 0, which is correct — any product chain through 0 is broken.
**The two-pass alternative:** Scan left-to-right tracking prefix products, reset on 0. Scan right-to-left tracking suffix products, reset on 0. The answer is the maximum of all non-zero prefix/suffix products. This handles even numbers of negatives elegantly.
**Odd number of negatives:** The maximum product comes from EITHER the left portion (excluding the rightmost negative) OR the right portion (excluding the leftmost negative). The dual min/max tracking handles this implicitly.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All subarray products computed explicitly |
| Optimal | O(n) | O(1) | Single pass tracking maxP and minP, with swap trick |
Pattern Recognition
✅ Maximum product contiguous subarray ✅ Contains negative numbers (can flip product sign) ✅ Track both max AND min simultaneously ✅ Swap trick when current element is negative **LeetCode Trigger Phrases:** → "maximum product subarray" → "array with positive, negative, and zero values" + maximize product → "contiguous subarray" + product
Bhagavad Gita 5.18
विद्याविनयसंपन्ने ब्राह्मणे गवि हस्तिनि। शुनि चैव श्वपाके च पण्डिताः समदर्शिनः॥
The wise see with equal vision a learned Brahmin, a cow, an elephant, a dog, and an outcast.
Connection: The algorithm treats positive and negative numbers with perfect equanimity — not dismissing negative values as purely harmful (they can multiply into the greatest product). Like the wise person who sees the divine in all beings regardless of their surface nature, the algorithm recognizes that the 'negative' element holds within it the seed of the maximum. By tracking minProd (the worst), we preserve the potential for the greatest transformation.