Maximum Subarray / Kadane's Algorithm: Running Sum, Reset When Negative

• Kadane's Algorithm – solves the Maximum Subarray problem by finding the contiguous slice of an array with the largest sum in a single linear pass.
• Running best-ending-here – at each index i, currentBest = Math.max(a[i], currentBest + a[i]) decides whether to extend or restart.
• Global best – globalBest = Math.max(globalBest, currentBest) captures the highest running sum seen at any position.
• O(n) time, O(1) space – the algorithm touches each element exactly once and uses only two extra variables.
• All-negative safety – initializing both values to a[0] ensures the answer is the least negative element, not zero, when every element is negative.

What is the Maximum Subarray problem?

The Maximum Subarray problem asks you to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. The subarray must contain at least one element. For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is the subarray [4, -1, 2, 1] with sum 6.

In banking terms, Rajesh at the National Bank of India has a sequence of daily net cash flows. The bank wants to find the single consecutive stretch of days that produced the largest total net gain.

Why does Kadane's Algorithm exist?

The brute-force approach tries every start and end pair and sums each slice, which is O(n^3), or O(n^2) with a running sum per start. Kadane's Algorithm reduces this to a single O(n) pass by noticing that the best subarray ending at position i depends only on the best subarray ending at position i - 1. This is a dynamic-programming observation that eliminates the need to look further back.

// Brute force: O(n^2) – checks every subarray
package com.bank.analysis;

import java.math.BigDecimal;

public class BruteForceMaxSubarray {
    public static BigDecimal maxSubarrayBrute(BigDecimal[] flows) {
        BigDecimal best = flows[0];
        for (int i = 0; i < flows.length; i++) {
            BigDecimal sum = BigDecimal.ZERO;
            for (int j = i; j < flows.length; j++) {
                sum = sum.add(flows[j]);
                if (sum.compareTo(best) > 0) {
                    best = sum;
                }
            }
        }
        return best;
    }
}

How does Kadane's Algorithm work internally?

You keep two values. The first, currentBest, is the largest sum of any subarray ending exactly at the current position. The second, globalBest, is the largest sum seen anywhere so far. Both are initialized to the first element.

For each remaining element you set currentBest to the maximum of the element alone and the element plus the previous currentBest. If the previous currentBest was negative, adding it only hurts, so the element alone wins and the run effectively resets. Then you set globalBest to the maximum of globalBest and currentBest.

Array:   [-2,  1, -3,  4, -1,  2,  1, -5,  4]
curBest: [-2,  1, -2,  4,  3,  5,  6,  1,  5]
gBest:   [-2,  1,  1,  4,  4,  5,  6,  6,  6]
                          ^--- best subarray starts here

How do you implement Kadane's Algorithm? (with code)

package com.bank.analysis;

import java.math.BigDecimal;

public class KadaneMaxSubarray {

    public static BigDecimal maxSubarraySum(BigDecimal[] flows) {
        if (flows == null || flows.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }
        BigDecimal currentBest = flows[0];
        BigDecimal globalBest = flows[0];

        for (int i = 1; i < flows.length; i++) {
            // Extend the previous run or start fresh
            currentBest = flows[i].max(currentBest.add(flows[i]));
            // Track the best seen so far
            globalBest = globalBest.max(currentBest);
        }
        return globalBest;
    }

    public static void main(String[] args) {
        BigDecimal[] dailyFlows = {
            new BigDecimal("-200"), new BigDecimal("1500"),
            new BigDecimal("-300"), new BigDecimal("4000"),
            new BigDecimal("-100"), new BigDecimal("2000"),
            new BigDecimal("1000"), new BigDecimal("-5000"),
            new BigDecimal("4000")
        };
        System.out.println("Max subarray sum: " + maxSubarraySum(dailyFlows));
    }
}

Max subarray sum: 8100

How do you recover the actual subarray indices?

Tracking the sum alone is not enough when the analyst needs to know which days formed the best stretch. You keep a tentative start index that you move to the current position whenever the run resets, and you record the start and end whenever globalBest improves.

package com.bank.analysis;

import java.math.BigDecimal;

public class KadaneWithIndices {

    public static int[] maxSubarrayIndices(BigDecimal[] flows) {
        BigDecimal currentBest = flows[0];
        BigDecimal globalBest = flows[0];
        int tempStart = 0, bestStart = 0, bestEnd = 0;

        for (int i = 1; i < flows.length; i++) {
            if (flows[i].compareTo(currentBest.add(flows[i])) > 0) {
                currentBest = flows[i];
                tempStart = i;  // reset: start a new run here
            } else {
                currentBest = currentBest.add(flows[i]);
            }
            if (currentBest.compareTo(globalBest) > 0) {
                globalBest = currentBest;
                bestStart = tempStart;
                bestEnd = i;
            }
        }
        return new int[]{bestStart, bestEnd};
    }
}

What happens with an all-negative array?

If every number is negative, the answer is the single largest (least negative) element, not zero. A naive implementation that initializes currentBest and globalBest to zero would wrongly return zero, implying an empty subarray. Initializing both to the first element guarantees the algorithm returns the least negative value.

// Wrong: initializing to zero
BigDecimal cur = BigDecimal.ZERO, best = BigDecimal.ZERO;
// For [-3, -5, -1, -8] this returns 0, which is incorrect

// Correct: initializing to first element
BigDecimal cur = flows[0], best = flows[0];
// For [-3, -5, -1, -8] this correctly returns -1

How is this different from the Maximum Product Subarray?

| Aspect | Maximum Sum (Kadane's) | Maximum Product |
|---|---|---|
| Operation | Addition | Multiplication |
| State needed | One running value (currentBest) | Two running values (maxProduct, minProduct) |
| Sign flip concern | No – adding a negative just reduces the sum | Yes – multiplying by a negative flips max and min |
| Reset condition | When extending is worse than starting fresh | Same, but must also swap max and min on negative |
| Zero handling | No special case | Zero resets both running products to zero |
| Time and space | O(n) time, O(1) space | O(n) time, O(1) space |

What are the edge cases?

Several edge cases are important for correctness.

• Single element – the answer is that element itself.
• All negative – the answer is the largest (least negative) element.
• All positive – the entire array is the answer because there is never a reason to reset.
• Zeros in the array – zeros do not cause a reset; extending by zero does not hurt. The run resets only if carrying forward produces a value below the current element alone.
• Empty array – the algorithm should reject this with an exception since at least one element is required.

// Edge case: single element
BigDecimal[] single = { new BigDecimal("500") };
// Returns 500

// Edge case: all positive
BigDecimal[] allPos = {
    new BigDecimal("100"), new BigDecimal("200"), new BigDecimal("300")
};
// Returns 600 (entire array)

What about time complexity and space complexity?

Kadane's Algorithm visits each element exactly once, so it runs in O(n) time. It uses only two extra variables (currentBest and globalBest), so it uses O(1) extra space. Adding index tracking adds a constant number of extra variables and does not change the complexity.

| Approach | Time | Space |
|---|---|---|
| Brute force (all pairs) | O(n^2) | O(1) |
| Divide and conquer | O(n log n) | O(log n) stack |
| Kadane's Algorithm | O(n) | O(1) |

What should a senior engineer know?

A senior engineer should understand that Kadane's is a dynamic-programming idea where the recurrence is dp[i] = max(a[i], dp[i-1] + a[i]) and globalBest = max(globalBest, dp[i]). The dp array is never materialized because each step depends only on the previous value, which is why it collapses to O(1) space.

For money, always use BigDecimal with add and max via compareTo so sums are exact. In a production banking system at the National Bank of India, Pankaj (the architect) would insist on this to avoid floating-point drift across a long series of daily net flows.

What are common interview follow-up questions?

• Can you do it in O(n)? – Yes, Kadane's is O(n).
• What if you want the indices? – Track tempStart, bestStart, and bestEnd as shown above.
• What if all elements are negative? – Initialize to the first element, not zero.
• What about the maximum product subarray? – Track both max and min products because negatives flip signs.
• What about a circular array? – The answer is the maximum of Kadane's on the linear array and the total sum minus the minimum subarray sum (Kadane's inverted).