Kadane's AlgorithmMediumO(n) time · O(1) space

Maximum Absolute Sum of Any Subarray

Bhagavad Gita — The Absolute Measure of Karma — Maximum Deviation from Zero

धनं वा ऋणं वा — परमं मूल्यम् उभयोः। निरपेक्षं मापनं यत्र — तत् सत्यं सर्वोत्तमम्॥

*Positive or negative — the absolute measure of both is what matters. Where the measurement is impartial — there lies the greatest truth.*

The Story

In the divine court after the Kurukshetra war, Lord Yama reviewed the karma ledger. Each soul's actions were recorded as a sequence of values — positive for merit, negative for sin. The absolute measure of a soul's karma — its maximum deviation from perfect neutrality in either direction — determined how dramatically it would experience its next life.

The divine accountant Chitragupta was asked: "For a given karmic sequence, what is the maximum absolute sum of any contiguous sub-life?"

Mathematically: find the subarray with the maximum absolute value of its sum — whether the sum is highly positive (great merit) or highly negative (grave sin).

"The answer," Chitragupta realized, "is simply the maximum of two quantities:" 1. The maximum subarray sum (standard Kadane — most positive) 2. The absolute value of the minimum subarray sum (negated Kadane — most negative in magnitude)

"The maximum absolute sum = max(maxSubarraySum, abs(minSubarraySum))"

This is because: - The subarray with the largest positive sum maximizes positive absolute value - The subarray with the most negative sum maximizes negative absolute value - The answer is whichever of these is larger in magnitude

Chitragupta demonstrated with `[1, -3, 2, 3, -4]`:

**Kadane for Maximum:** - i=0: curr=1, max=1 - i=1: curr=max(-3,-2)=-2, max=1 - i=2: curr=max(2,0)=2, max=2 - i=3: curr=max(3,5)=5, max=5 - i=4: curr=max(-4,1)=1, max=5 maxSum = 5 (subarray [2,3])

**Kadane for Minimum:** - i=0: curr=1, min=1 - i=1: curr=min(-3,-2)=-3, min=-3 - i=2: curr=min(2,-1)=-1, min=-3 - i=3: curr=min(3,2)=2, min=-3 - i=4: curr=min(-4,-2)=-4, min=-4 minSum = -4 (subarray [-4])

Answer = max(5, abs(-4)) = max(5, 4) = **5**

"The soul with karma sequence [1,-3,2,3,-4] achieved a maximum absolute karma of 5," Chitragupta declared, "through the meritorious stretch [2,3]."

"But what about `[-3, -5, -2]`?" maxSum = Kadane max = -2 (single element, least negative) minSum = Kadane min = -10 (entire array) Answer = max(-2, abs(-10)) = max(-2, 10) = **10**

"This soul's most extreme karma stretch was -10 — entirely sinful actions. The maximum absolute sum is 10."

"The elegance," Chitragupta noted, "is that we run both Kadane variants simultaneously in a single pass. Four variables: `curMax`, `curMin`, `maxSum`, `minSum`. Two decisions per element. Two comparisons for the answer."

The karmic ledger was closed. Every soul had been measured by the absolute maximum of its best and worst contiguous stretch — not by average, not by total, but by the peak deviation from zero in either direction.

This is the dual Kadane technique for maximum absolute sum of any subarray.

Chitragupta's First Instinct

Try every subarray. Compute the sum. Track the maximum absolute sum. O(n²) time.

java

public int maxAbsoluteSumBruteForce(int[] nums) {
    int maxAbs = 0;
    
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end < nums.length; end++) {
            sum += nums[end];
            maxAbs = Math.max(maxAbs, Math.abs(sum));
        }
    }
    
    return maxAbs;
}

Chitragupta's Dual Kadane Wisdom

Run both Kadane variants simultaneously: - Track `curMax` and `maxSum` (maximum subarray sum) - Track `curMin` and `minSum` (minimum subarray sum, most negative) Answer = max(maxSum, abs(minSum)) Single pass with 4 variables.

java

public int maxAbsoluteSum(int[] nums) {
    int curMax = 0, maxSum = 0;
    int curMin = 0, minSum = 0;
    
    for (int n : nums) {
        // Kadane for maximum (reset when negative)
        curMax = Math.max(0, curMax + n);
        maxSum = Math.max(maxSum, curMax);
        
        // Kadane for minimum (reset when positive)
        curMin = Math.min(0, curMin + n);
        minSum = Math.min(minSum, curMin);
    }
    
    // Maximum absolute sum is either the max positive or max negative magnitude
    return Math.max(maxSum, Math.abs(minSum));
}

// Test
public static void main(String[] args) {
    System.out.println(new Solution().maxAbsoluteSum(new int[]{1,-3,2,3,-4}));  // 5
    System.out.println(new Solution().maxAbsoluteSum(new int[]{2,-5,1,-4,3,-2})); // 8
    System.out.println(new Solution().maxAbsoluteSum(new int[]{-3,-5,-2}));      // 10
}

Step-by-Step Walkthrough

nums = [1, -3, 2, 3, -4]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Init: curMax=0, maxSum=0, curMin=0, minSum=0

n=1:
  curMax=max(0,0+1)=1, maxSum=1
  curMin=min(0,0+1)=0, minSum=0

n=-3:
  curMax=max(0,1-3)=max(0,-2)=0, maxSum=1
  curMin=min(0,0-3)=-3, minSum=-3

n=2:
  curMax=max(0,0+2)=2, maxSum=2
  curMin=min(0,-3+2)=min(0,-1)=-1, minSum=-3

n=3:
  curMax=max(0,2+3)=5, maxSum=5
  curMin=min(0,-1+3)=min(0,2)=0, minSum=-3

n=-4:
  curMax=max(0,5-4)=1, maxSum=5
  curMin=min(0,0-4)=-4, minSum=-4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Answer = max(maxSum=5, abs(minSum=-4)) = max(5,4) = 5
✅ Return 5

Deep Insight

**Why initialize curMax=0 and curMin=0 here?** This implementation uses the `max(0, ...)` form of Kadane where we reset on 0 (not on the previous element). This naturally handles the case where no element is included (empty subarray = sum 0). Since absolute sum is always non-negative, and the problem guarantees a non-empty subarray answer, this is safe.

**Why `max(maxSum, abs(minSum))`?** The maximum absolute sum comes from either: 1. The subarray with the largest positive sum (maxSum) 2. The subarray with the most negative sum (minSum), whose absolute value might be larger

**Connection to negative Kadane:** Running Kadane for maximum on the NEGATED array gives `-minSum`. So `abs(minSum) = max_subarray_sum(-nums)`. This confirms the approach.

**Edge case — all zeros:** maxSum=0, minSum=0, answer=0.

**When does the minimum subarray win?** When a deeply negative subarray has greater magnitude than any positive subarray. e.g., `[1, -100, 1]`: maxSum=1, minSum=-100, answer=100.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	All O(n²) subarrays with abs(sum) tracked
Optimal	O(n)	O(1)	One pass, four variables for dual Kadane

Pattern Recognition

✅ Maximum ABSOLUTE sum (not just maximum sum)
✅ Run Kadane for both maximum and minimum
✅ Answer = max(maxSum, abs(minSum))
✅ Four variables: curMax, maxSum, curMin, minSum

**LeetCode Trigger Phrases:**
→ "maximum absolute sum of any subarray"
→ "the absolute value of the subarray sum is maximized"
→ "absolute" + maximize + contiguous subarray

Bhagavad Gita 13.27

समं सर्वेषु भूतेषु तिष्ठन्तं परमेश्वरम्। विनश्यत्स्वविनश्यन्तं यः पश्यति स पश्यति॥

One who sees the Supreme Lord equally present in all beings — in the perishable and the imperishable — that person truly sees.

Connection: The algorithm measures karma's absolute value — it treats intense merit and intense sin with equal impartiality, tracking both maximal positive and minimal negative simultaneously. Like the divine perspective described in the Gita, which sees equally in all beings regardless of surface appearance, the algorithm's dual Kadane sees both extremes as equally valid manifestations of the absolute. The greatest karma — whether positive or negative — reveals the soul's maximum capacity for intensity.