Maximum Absolute Sum of Any Subarray

• Absolute-value decomposition – |sum| is large when sum is very positive or very negative, so the problem splits into two Kadane passes.
• Dual Kadane – run max-Kadane and min-Kadane simultaneously: curMax = max(nums[i], curMax + nums[i]) and curMin = min(nums[i], curMin + nums[i]).
• Answer – max(globalMax, abs(globalMin)) after a single O(n) pass.
• Prefix-sum alternative – the answer also equals max(prefix) - min(prefix) over the running prefix sums including an implicit zero.
• Complexity – O(n) time, O(1) space for both approaches.

What is the problem?

Given an array of integers (positive, negative, or zero), find the maximum absolute value among the sums of all contiguous non-empty subarrays. The answer is always non-negative.

Why does the problem decompose into two Kadanes?

The absolute value of a subarray sum is large in two situations: when the sum is a large positive number, or when it is a large negative number. Since absolute value is not linear, a single Kadane pass cannot optimize it directly. Instead, we find the maximum subarray sum (most positive run) and the minimum subarray sum (most negative run), then take the larger magnitude.

How do you implement dual Kadane?

package com.bank.service;

public class LiquiditySwingAnalyzer {

    public static long maxAbsSubarraySum(int[] swings) {
        long curMax = swings[0], globalMax = swings[0];
        long curMin = swings[0], globalMin = swings[0];

        for (int i = 1; i < swings.length; i++) {
            curMax = Math.max(swings[i], curMax + swings[i]);
            globalMax = Math.max(globalMax, curMax);

            curMin = Math.min(swings[i], curMin + swings[i]);
            globalMin = Math.min(globalMin, curMin);
        }
        return Math.max(globalMax, Math.abs(globalMin));
    }

    public static void main(String[] args) {
        // Daily net cash swings (rupees in thousands) for Rajesh's account
        int[] swings = {2, -5, 1, -4, 3, -2};
        System.out.println("Max absolute subarray sum: " + maxAbsSubarraySum(swings));
    }
}

Max absolute subarray sum: 8

The most negative run is [-5, 1, -4] with sum -8, and |(-8)| = 8 beats the most positive run.

How does the prefix-sum approach work?

Every subarray sum is the difference of two prefix sums. The maximum absolute subarray sum equals the maximum prefix sum minus the minimum prefix sum, including an implicit zero at index -1.

public static long maxAbsPrefixSum(int[] swings) {
    long prefix = 0, maxPre = 0, minPre = 0;
    for (int s : swings) {
        prefix += s;
        maxPre = Math.max(maxPre, prefix);
        minPre = Math.min(minPre, prefix);
    }
    return maxPre - minPre;
}

How are the two approaches related?

| Feature | Dual Kadane | Prefix Sum |
|---|---|---|
| Idea | max subarray sum vs min subarray sum | max prefix minus min prefix |
| Passes | 1 pass, 4 variables | 1 pass, 3 variables |
| Time | O(n) | O(n) |
| Space | O(1) | O(1) |
| Elegance | explicit max/min tracking | simpler code |

Both give the same answer because any subarray sum is a prefix-sum difference, and the maximum such difference pairs the highest prefix with the lowest.

What are edge cases?

• All positive: the answer is the total sum (the whole array).
• All negative: the answer is the absolute value of the total sum.
• Single element: the answer is the absolute value of that element.
• Array with zeros: zeros can be part of either the max or min subarray.

What are common mistakes?

// Wrong: seeding globalMax and globalMin at 0
long globalMax = 0, globalMin = 0; // wrong for single-element arrays

// Correct: seed from the first element
long globalMax = swings[0], globalMin = swings[0];

What should a senior engineer know?

Absolute-value objectives almost always split into a maximize branch and a minimize branch. Recognizing this pattern lets you reuse known algorithms (Kadane) instead of inventing a bespoke one. The prefix-sum formulation is a second valid lens that signals flexibility.

For monetary values in the banking domain, accumulate in a long or BigDecimal to avoid overflow across long histories, since daily swings can span years of data.

What are common interview follow-up questions?

• What if you need the actual subarray, not just the sum?
• How would you handle a circular array?
• Can you solve this with divide and conquer?