Kadane's Algorithm — All-Negative Input Returns $340k Loss

Maximum subarray sum — finding the contiguous segment of an array with the largest sum — appears in financial analytics (peak profitability windows), signal processing (strongest signal bursts), and genomics (highest-expression DNA regions). The naive approach checks every start-end pair: O(n²). For a 10,000-element array, that is 50 million operations. Kadane's Algorithm solves it in a single linear pass: O(n), O(1) space.

The algorithm maintains two values: currentSum (the best sum ending at the current position) and maxSumFound (the global best). At each element, it decides: extend the current subarray or start fresh. The decision is greedy and provably correct — a negative prefix can never improve a subarray's sum, so it is always discarded.

The common misconception is that this is 'just a DP problem.' While Kadane's recurrence (dp[i] = max(arr[i], dp[i-1] + arr[i])) is a DP formulation, the O(1) space optimization makes it a distinct pattern. Understanding the greedy intuition — not just the recurrence — is what separates candidates who can explain it on a whiteboard from those who just memorize the code.

Why Kadane's Algorithm Fails on All-Negative Arrays

Kadane's algorithm finds the maximum subarray sum in O(n) time by scanning left to right, maintaining two variables: current sum (the best sum ending at the current position) and global max (the best sum seen so far). At each step, it decides whether to extend the current subarray or start fresh at the current element. The core mechanic is the recurrence: current = max(element, current + element).

In practice, the algorithm works because it exploits the property that any maximum subarray must start at a point where the prefix sum is minimal. It avoids recomputing overlapping subproblems by carrying forward only the useful prefix. The critical nuance: when all inputs are negative, the standard implementation returns the largest negative number (the least loss), not zero. This is correct behavior for the problem as originally defined — maximum subarray sum must be non-empty.

Use Kadane's when you need the maximum sum of any contiguous subarray in a one-dimensional array. Real systems use it for financial time-series anomaly detection, sensor data peak identification, and resource allocation optimization. It's the canonical example of dynamic programming reduced to linear time with constant space — O(1) extra memory.

How Kadane's Algorithm Works — Plain English

Kadane's algorithm finds the maximum-sum contiguous subarray in O(n) time and O(1) space. The key insight: at each position, either extend the previous subarray or start a fresh one — whichever gives a higher sum.

Step-by-step: 1. Initialize current_sum = arr[0], max_sum = arr[0]. 2. For i from 1 to n-1: a. current_sum = max(arr[i], current_sum + arr[i]). b. max_sum = max(max_sum, current_sum). 3. Return max_sum.

Worked example on [-2, 1, -3, 4, -1, 2, 1, -5, 4]: i=0: current=-2, max=-2. i=1: current=max(1,-2+1)=1. max=1. i=2: current=max(-3,1-3)=-2. max=1. i=3: current=max(4,-2+4)=4. max=4. i=4: current=max(-1,4-1)=3. max=4. i=5: current=max(2,3+2)=5. max=5. i=6: current=max(1,5+1)=6. max=6. i=7: current=max(-5,6-5)=1. max=6. i=8: current=max(4,1+4)=5. max=6. Maximum sum subarray = 6, from [4,-1,2,1].

package io.thecodeforge.algo;

import java.util.Arrays;

public class KadanePlainEnglish {

    public static long findMaxSubarraySum(int[] arr) {
        long currentSum = arr[0];
        long maxSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // Core decision: extend or restart?
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Max subarray sum: " + findMaxSubarraySum(arr)); // 6

        // Edge case: all negatives
        int[] allNeg = {-8, -3, -6, -2, -5};
        System.out.println("\nAll negatives: " + findMaxSubarraySum(allNeg)); // -2

        // Edge case: single element
        int[] single = {42};
        System.out.println("Single element: " + findMaxSubarraySum(single)); // 42
    }
}

The Core Intuition — Why the Greedy Decision Works

Before touching code, let's lock in the mental model. At every index i, you face exactly one binary choice: does the current element join the existing subarray, or does it become the start of a brand-new one?

The rule is beautifully simple: if your running sum so far is negative, it's dead weight. Carrying it into the next element can only make that element's contribution worse. So you drop it. You set your running sum equal to the current element and start fresh. If your running sum is positive, it's a booster — keep it.

This is a greedy decision, and it's correct because the optimal subarray can never benefit from a negative prefix. Think about it: if the subarray [3, -5, 2, 4] were the optimal answer, you could always remove the [3, -5] prefix (which sums to -2) and get [2, 4] with a larger sum. That contradiction proves negative prefixes can never be part of the true maximum subarray.

The algorithm tracks two values at all times: currentSum (the best sum ending at the current position) and maxSumFound (the global best seen so far). Every step, you update both. When the loop finishes, maxSumFound is your answer.

package io.thecodeforge.algo;

public class KadaneBasic {

    /**
     * Finds the maximum sum of any contiguous subarray.
     * Uses Kadane's Algorithm — O(n) time, O(1) space.
     */
    public static long findMaxSubarraySum(int[] profits) {
        // Seed with first element — NEVER seed with 0
        long currentSum = profits[0];
        long maxSumFound = profits[0];

        for (int day = 1; day < profits.length; day++) {
            // Core decision: extend the current run, or start fresh today?
            currentSum = Math.max(profits[day], currentSum + profits[day]);
            maxSumFound = Math.max(maxSumFound, currentSum);
        }

        return maxSumFound;
    }

    public static void main(String[] args) {
        int[] dailyProfits = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max subarray sum: " + findMaxSubarraySum(dailyProfits)); // 6

        int[] allLosses = {-8, -3, -6, -2, -5};
        System.out.println("All negatives: " + findMaxSubarraySum(allLosses)); // -2

        int[] oneDay = {42};
        System.out.println("Single element: " + findMaxSubarraySum(oneDay)); // 42
    }
}

Tracking the Actual Subarray — Not Just the Sum

The basic version tells you the maximum sum, but real-world use cases often need to know which subarray produced it. Imagine a financial dashboard that needs to highlight the exact date range of peak profitability — the number alone isn't enough.

Extending Kadane's to track indices takes almost no extra code. You record a potentialStart index whenever you decide to restart (i.e., when starting fresh beats extending). The moment that fresh start leads to a new global maximum, you commit it: you update bestStart, bestEnd, and maxSumFound together as an atomic snapshot.

This is a subtle but important pattern. You only want to commit the start index when you've confirmed it produced a better result, not optimistically when you reset. That distinction separates a correct implementation from a buggy one that snaps the wrong start index.

package io.thecodeforge.algo;

public class KadaneWithIndices {

    static class SubarrayResult {
        final long maxSum;
        final int startIndex;
        final int endIndex;

        SubarrayResult(long maxSum, int startIndex, int endIndex) {
            this.maxSum = maxSum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public String toString() {
            return String.format("Max Sum: %d | Start: %d | End: %d", maxSum, startIndex, endIndex);
        }
    }

    /**
     * Kadane's extended to return subarray boundaries. O(n) time, O(1) space.
     */
    public static SubarrayResult findMaxSubarray(int[] values) {
        long currentSum = values[0];
        long maxSumFound = values[0];

        int potentialStart = 0;
        int bestStart = 0;
        int bestEnd = 0;

        for (int index = 1; index < values.length; index++) {
            // If starting fresh beats extending, reset and mark tentative start
            if (values[index] > currentSum + values[index]) {
                currentSum = values[index];
                potentialStart = index;
            } else {
                currentSum += values[index];
            }

            // Only commit boundaries when we confirm a new global maximum
            if (currentSum > maxSumFound) {
                maxSumFound = currentSum;
                bestStart = potentialStart;
                bestEnd = index;
            }
        }

        return new SubarrayResult(maxSumFound, bestStart, bestEnd);
    }

    public static void main(String[] args) {
        int[] stockReturns = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        SubarrayResult result = findMaxSubarray(stockReturns);
        System.out.println(result);

        // Print the actual subarray
        System.out.print("Subarray: [");
        for (int i = result.startIndex; i <= result.endIndex; i++) {
            System.out.print(stockReturns[i] + (i < result.endIndex ? ", " : "]\n"));
        }
    }
}

Kadane's vs. Brute Force vs. Divide and Conquer — Choosing Wisely

Understanding why Kadane's is the right choice requires knowing what you're giving up and getting compared to the alternatives.

The brute-force approach uses two nested loops to check every (start, end) pair. It's O(n²) and straightforward to reason about, which makes it fine for arrays under a few hundred elements in non-critical paths. Divide and Conquer solves the problem in O(n log n) — better than brute force, but still worse than Kadane's. Its advantage is that it's parallelizable: you can split the array across multiple cores and merge results, which matters in distributed systems processing massive datasets.

Kadane's wins on pure time complexity and simplicity for the single-machine case. One pass, two variables, done. The only scenario where you'd reach for Divide and Conquer over Kadane's is when you need to run this computation across distributed partitions where a central linear scan isn't possible — think MapReduce jobs over terabyte-scale log files.

For coding interviews, Kadane's is the expected answer the moment you see 'maximum subarray.' Mentioning the Divide and Conquer alternative shows depth and will genuinely impress a senior interviewer.

package io.thecodeforge.algo;

public class KadaneVsBruteForce {

    /** Brute Force: O(n^2) */
    public static long bruteForceMaxSum(int[] values) {
        long globalMax = values[0];
        for (int start = 0; start < values.length; start++) {
            long runningSum = 0;
            for (int end = start; end < values.length; end++) {
                runningSum += values[end];
                globalMax = Math.max(globalMax, runningSum);
            }
        }
        return globalMax;
    }

    /** Kadane's: O(n) */
    public static long kadaneMaxSum(int[] values) {
        long currentSum = values[0];
        long globalMax = values[0];
        for (int index = 1; index < values.length; index++) {
            currentSum = Math.max(values[index], currentSum + values[index]);
            globalMax = Math.max(globalMax, currentSum);
        }
        return globalMax;
    }

    public static void main(String[] args) {
        int[] data = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        long t1 = System.nanoTime();
        long brute = bruteForceMaxSum(data);
        long bruteTime = System.nanoTime() - t1;

        long t2 = System.nanoTime();
        long kadane = kadaneMaxSum(data);
        long kadaneTime = System.nanoTime() - t2;

        System.out.println("Brute: " + brute + " (" + bruteTime + " ns)");
        System.out.println("Kadane: " + kadane + " (" + kadaneTime + " ns)");
        System.out.println("Match: " + (brute == kadane));
    }
}

The Naive Approach: Why You'd Never Ship It (But Should Still Understand)

Before you blindly trust Kadane, you need to know what you're replacing. The brute-force solution iterates over every possible subarray using two nested loops. Outer loop picks the start index. Inner loop expands to the end, accumulating sum and tracking the maximum. Time complexity: O(n²). Space: O(1). That's fine for a toy array of 100 elements. For a production data pipeline ingesting 10 million sensor readings? Your service will timeout before you get your first cup of coffee.

The WHY is simple: this approach doesn't exploit any structure of the problem. It's the equivalent of checking every drawer in a house to find a key when you know it's probably in the kitchen. It works, but it's embarrassingly inefficient. You'll see this pattern in junior code reviews — they solve the problem, but they don't understand the cost. Understanding the naive approach is critical because it frames why Kadane's linear scan is not just clever, but necessary for any system that needs to scale.

// io.thecodeforge — dsa tutorial

public class NaiveMaxSubarray {
    public static int bruteForceMaxSum(int[] nums) {
        int maxSum = nums[0];
        
        for (int start = 0; start < nums.length; start++) {
            int currentSum = 0;
            for (int end = start; end < nums.length; end++) {
                currentSum += nums[end];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] prices = {2, 3, -8, 7, -1, 2, 3};
        System.out.println("Max subarray sum: " + bruteForceMaxSum(prices));
    }
}

Kadane's Algorithm: The O(n) Solution That Actually Ships

Kadane's Algorithm is the production-grade solution. It's a single pass, O(n) time, O(1) space. The core insight: you carry forward a running sum (currentSum) only if it helps you. At each element, you decide: do I extend the existing subarray, or do I start fresh from this element? The decision is greedy — if currentSum + nums[i] is greater than nums[i], you extend. Otherwise, you reset. You then track the maximum of currentSum across all iterations.

Why does this work? Because any subarray that drags the sum down below the current element is poison. If the running sum ever goes negative, it can only reduce the potential of future elements. So you drop it. This is the exact same reasoning behind why you'd reject a team member who constantly derails progress — cut losses early. The beauty is that this single decision handles all cases, including the all-negative arrays (the current element itself becomes the new candidate). One pass, no backtracking. That's how you write code that survives production.

// io.thecodeforge — dsa tutorial

public class KadaneAlgorithm {
    public static int kadaneMaxSum(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] sensorReadings = {2, 3, -8, 7, -1, 2, 3};
        System.out.println("Max subarray sum: " + kadaneMaxSum(sensorReadings));
        
        int[] allNegative = {-5, -2, -8, -1};
        System.out.println("All negative case: " + kadaneMaxSum(allNegative));
    }
}