Maximum Subarray (Kadane's Algorithm): running sum reset at negatives

• Kadane's algorithm – a linear dynamic programming scan that maintains the best subarray sum ending at the current index.
• Decision at each step – current = max(num, current + num) either extends the running subarray or restarts from the current element.
• Global tracking – answer = max(answer, current) updates the best sum seen so far.
• Initialization – both current and answer start at the first element, not zero, to handle all-negative arrays correctly.
• Complexity – O(n) time, O(1) space.

What is the Maximum Subarray problem?

Given an integer array, find the contiguous subarray with the largest sum and return that sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray is [4, -1, 2, 1] with sum 6.

At the National Bank of India, analysts review daily net cash flows and need to find the most profitable contiguous window of days.

How does Kadane's algorithm work?

Kadane's algorithm scans the array once, maintaining two values:

• current: the maximum subarray sum ending at the current index.
• best: the maximum sum seen so far across all indices.

At each element, the decision is: should we extend the previous subarray, or start a fresh one here?

current = Math.max(num, current + num);
best = Math.max(best, current);

If current + num is less than num alone, the running sum was negative and dragging the total down, so we discard it and start fresh.

package com.bank.analytics;

public class MaxSubarraySum {
    public static int kadane(int[] cashFlows) {
        int current = cashFlows[0];
        int best = cashFlows[0];

        for (int i = 1; i < cashFlows.length; i++) {
            current = Math.max(cashFlows[i], current + cashFlows[i]);
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] dailyFlows = {-200, 150, -50, 400, -100, 250, 100, -500, 300};
        System.out.println("Maximum subarray sum: " + kadane(dailyFlows));
    }
}

Maximum subarray sum: 750

Why initialize to the first element and not zero?

If all elements are negative, initializing to zero would return zero, which is wrong because zero is not a valid subarray sum. Initializing to the first element ensures the answer is the largest single element in an all-negative array.

// Wrong: initializing to zero
int current = 0, best = 0;
// For [-5, -3, -1], returns 0 instead of -1

// Correct: initializing to first element
int current = nums[0], best = nums[0];
// For [-5, -3, -1], correctly returns -1

How to recover the actual subarray indices?

To find not just the sum but the actual subarray, track candidate start and end indices.

package com.bank.analytics;

public class MaxSubarrayWithIndices {
    public static void findMaxSubarray(int[] cashFlows) {
        int current = cashFlows[0];
        int best = cashFlows[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < cashFlows.length; i++) {
            if (cashFlows[i] > current + cashFlows[i]) {
                current = cashFlows[i];
                tempStart = i;
            } else {
                current = current + cashFlows[i];
            }
            if (current > best) {
                best = current;
                start = tempStart;
                end = i;
            }
        }
        System.out.println("Max sum: " + best);
        System.out.println("From day " + start + " to day " + end);
    }

    public static void main(String[] args) {
        int[] dailyFlows = {-200, 150, -50, 400, -100, 250, 100, -500, 300};
        findMaxSubarray(dailyFlows);
    }
}

Max sum: 750
From day 1 to day 6

What is the time and space complexity?

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

Kadane's algorithm is optimal. No algorithm can do better than O(n) because every element must be examined at least once.

How does it compare to the brute-force approach?

The brute force checks every possible subarray and computes its sum, which is O(n^2). Kadane's key insight is that the maximum subarray ending at position i depends only on the maximum subarray ending at position i-1, making it a simple dynamic programming recurrence.

// Brute force: O(n^2)
for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += nums[j];
        best = Math.max(best, sum);
    }
}

// Kadane: O(n)
for (int i = 1; i < n; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
}

What are the edge cases?

• Single element: return that element.
• All negative: return the largest (least negative) element.
• All positive: the entire array is the maximum subarray.
• Contains zeros: zeros neither help nor hurt; the algorithm handles them naturally.

int[] single   = {42};           // result: 42
int[] allNeg   = {-5, -3, -1};   // result: -1
int[] allPos   = {1, 2, 3, 4};   // result: 10
int[] withZero = {-1, 0, -2};    // result: 0

What are common mistakes?

The most common mistake is initializing current and best to zero instead of the first element. Another mistake is forgetting to update best after every step.

// Wrong: best updated only at the end
for (int i = 1; i < n; i++) {
    current = Math.max(nums[i], current + nums[i]);
}
best = current; // misses peaks that occurred earlier

// Correct: best updated inside the loop
for (int i = 1; i < n; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
}

What should a senior engineer know?

• Variant: Maximum Subarray Product requires tracking both max and min because a negative times a negative becomes positive.
• Variant: Circular Maximum Subarray uses the identity that the circular max is the total sum minus the minimum subarray sum.
• Divide and Conquer splits the array in half, recurses on both sides, and combines by extending from the midpoint. It is O(n log n) and useful for educational purposes but not practical.
• Prefix sum approach computes prefix sums and finds the max difference between any later prefix sum and an earlier one, which is equivalent to Kadane's.

What are common interview follow-up questions?

• Return the actual subarray, not just the sum. (Track indices.)
• What if the array is circular? (Total minus minimum subarray.)
• What if you must pick at least k elements? (Combine prefix sums with a sliding window.)
• Maximum product subarray? (Track both max and min products.)