Maximum Subarray Sum (Kadane's Algorithm)

• Kadane's algorithm finds the maximum sum of any contiguous non-empty subarray in a single linear pass.
• At each position, compute currentMax = Math.max(nums[i], currentMax + nums[i]).
• This captures the decision: extend the running sum or restart from the current element.
• Track globalMax = Math.max(globalMax, currentMax) to remember the best.
• Seed both variables from the first element and iterate from the second.
• Time is O(N) and space is O(1).

What is the Maximum Subarray Sum problem?

Given an array of integers that may include negative numbers, find the maximum sum obtainable from any contiguous non-empty subarray. This is one of the most fundamental dynamic programming problems, solved optimally by Kadane's algorithm in linear time.

For example, given [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray sum is 6, from the subarray [4, -1, 2, 1].

How does Kadane's algorithm work?

The insight is that the maximum subarray must end at some position. If for every position we compute the maximum sum of a subarray ending exactly there, the overall answer is the largest of those per-position values.

package com.bank.service;

public class MaxSubarraySumService {

    /**
     * Finds the most profitable continuous trading stretch.
     * Used by the National Bank of India risk management team.
     */
    public static long maxSubarraySum(long[] profitLoss) {
        long currentMax = profitLoss[0];
        long globalMax = profitLoss[0];

        for (int i = 1; i < profitLoss.length; i++) {
            currentMax = Math.max(profitLoss[i],
                                  currentMax + profitLoss[i]);
            globalMax = Math.max(globalMax, currentMax);
        }
        return globalMax;
    }

    public static void main(String[] args) {
        long[] profitLoss = {-20000, 10000, -30000, 40000,
                             -10000, 20000, 10000, -50000, 40000};
        System.out.println("Best continuous P&L: Rs." + maxSubarraySum(profitLoss));
    }
}

javac -d out com/bank/service/MaxSubarraySumService.java
java -cp out com.bank.service.MaxSubarraySumService

Best continuous P&L: Rs.60000

Why must you seed from the first element?

Because the subarray must be non-empty and the array may be all negative, you must start both currentMax and globalMax at nums[0] and iterate from index 1. Starting globalMax at zero would wrongly report zero for an all-negative array, when the correct answer is the single least-negative element.

// WRONG: seeds globalMax at 0
long globalMax = 0; // Returns 0 for [-5, -3, -1] instead of -1

// CORRECT: seeds from first element
long globalMax = profitLoss[0]; // Returns -1 for [-5, -3, -1]

How do you recover the subarray indices?

To find the actual start and end indices of the best subarray, track a tentative start that resets whenever you choose to restart, and commit the best start and end whenever the global maximum improves.

package com.bank.service;

public class MaxSubarrayWithIndices {

    public static void findBestStretch(long[] pnl) {
        long currentMax = pnl[0], globalMax = pnl[0];
        int tempStart = 0, bestStart = 0, bestEnd = 0;

        for (int i = 1; i < pnl.length; i++) {
            if (pnl[i] > currentMax + pnl[i]) {
                currentMax = pnl[i];
                tempStart = i; // Restart from here
            } else {
                currentMax = currentMax + pnl[i];
            }
            if (currentMax > globalMax) {
                globalMax = currentMax;
                bestStart = tempStart;
                bestEnd = i;
            }
        }
        System.out.println("Best stretch: day " + bestStart
            + " to day " + bestEnd + ", total: Rs." + globalMax);
    }

    public static void main(String[] args) {
        long[] pnl = {-20000, 10000, -30000, 40000,
                      -10000, 20000, 10000, -50000, 40000};
        findBestStretch(pnl);
    }
}

Best stretch: day 3 to day 6, total: Rs.60000

What is the recurrence behind Kadane's?

Define f(i) as the maximum sum of a subarray ending at index i. The recurrence is:

• f(0) = nums[0]
• f(i) = max(nums[i], f(i-1) + nums[i]) for i > 0

The answer is max(f(i)) over all i. Kadane's algorithm computes this in O(1) space by keeping only the previous f value.

What are the edge cases?

Several edge cases require attention.

• All negative: the answer is the single least-negative element.
• Single element: the answer is that element.
• All positive: the answer is the sum of the entire array.
• Large values: use long to prevent integer overflow on financial data.

package com.bank.core;

public class KadaneEdgeCases {
    public static void main(String[] args) {
        System.out.println(maxSum(new long[]{-5, -3, -1}));  // -1
        System.out.println(maxSum(new long[]{42}));           // 42
        System.out.println(maxSum(new long[]{1, 2, 3, 4}));  // 10
    }

    static long maxSum(long[] arr) {
        long cur = arr[0], best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur = Math.max(arr[i], cur + arr[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

-1
42
10

What is the time and space complexity?

Time is O(N): a single pass through the array. Space is O(1): two scalar variables. This is optimal because you must read every element at least once.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• DP collapsed to O(1) space: Kadane's is the canonical example of sequence DP where the state depends only on the previous position, so the full DP table collapses to a single variable.
• Divide and conquer alternative: the maximum subarray can also be found in O(N log N) using divide and conquer, but Kadane's O(N) dominates.
• Prefix sum view: the maximum subarray sum equals the maximum of prefix[i] - prefix[j] for j < i, which is equivalent to tracking the running minimum prefix sum.
• Overflow: for financial P&L data, always accumulate in long or BigDecimal.

What are common interview follow-up questions?

Interviewers often extend this problem.

• Minimum subarray sum: flip the comparison to Math.min (Kadane's mirror).
• Maximum product subarray: track both max and min products.
• Maximum subarray sum with one deletion: add a second DP state.
• Maximum sum circular subarray: combine max and min Kadane.