Find Maximum Sum Subarray using Kadane’s Algorithm

Title: Find Maximum Sum Subarray using Kadane’s Algorithm

Finding the contiguous subarray with the largest sum is one of the most frequently asked questions in coding interviews, and it is often the problem that introduces developers to dynamic programming. In this guide, you will learn how Kadane's Algorithm solves it in a single linear pass, why the naive approaches fall short, and how to trace, test, and extend the solution for follow-up interview questions.

Understanding the Problem

Given an array of integers that can include negative numbers, the goal is to find the contiguous subarray, containing at least one number, that has the largest possible sum, and return that sum. A subarray must be contiguous, so you cannot skip elements and pick them individually; you choose a start index and an end index and sum everything in between.

The naive approach checks every possible subarray, computing its sum and keeping track of the maximum. That works, but it costs O(n^2) time even with a running-sum optimization, or O(n^3) if each sum is recomputed from scratch. Kadane's Algorithm solves the same problem in O(n) time and O(1) extra space by recognizing a key insight: the maximum subarray ending at a given index either extends the best subarray ending at the previous index, or it starts fresh at the current element.

Approach: Kadane’s Algorithm Steps

1. Reject a null or empty array up front by throwing IllegalArgumentException, since the maximum subarray sum is undefined for zero elements.
2. Initialize two variables, maxEndingHere and maxSoFar, both set to nums[0].
3. Iterate through the array starting at index 1, since index 0 already seeded both variables.
4. At each index, decide whether to extend the running subarray or start a new one: maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]).
5. Update the global best whenever the running sum beats it: maxSoFar = Math.max(maxSoFar, maxEndingHere).
6. Continue until the loop reaches the end of the array, carrying only two running variables forward.
7. Return maxSoFar as the maximum subarray sum.

Java Program

public class MaxSumSubarray {

    public static int maxSubArraySum(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }

        int maxEndingHere = nums[0];
        int maxSoFar = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum subarray sum: " + maxSubArraySum(nums));
    }
}

Explanation of the Program

The method maxSubArraySum starts by validating the input array, immediately throwing an exception for a null or empty array so the caller finds out about the misuse at the call site instead of getting a misleading default value.

Both maxEndingHere and maxSoFar start at nums[0] because the smallest valid subarray is a single element, and seeding with the first element avoids a special case for arrays that are entirely negative.

Inside the loop, Math.max(nums[i], maxEndingHere + nums[i]) is the heart of the algorithm. It compares continuing the current run against starting over at the current element, and keeps whichever is larger. maxSoFar then captures the best value seen across every iteration, not just the most recent one.

By the time the loop finishes, maxSoFar holds the answer for the whole array, and the method returns it directly.

Step-by-Step Trace

For the input [3, -4, 5, -2, 6, -1, 2], the algorithm should return 10, coming from the subarray [5, -2, 6, -1, 2]. The table below traces every iteration starting at i = 1, since i = 0 only seeds the initial values.

At the end of each iteration, maxSoFar holds the maximum subarray sum found among all subarrays that end at or before that index.

Examples

Example 1: Array with Mixed Positive and Negative Numbers

For the classic input [-2, 1, -3, 4, -1, 2, 1, -5, 4], the best contiguous run is [4, -1, 2, 1], which sums to 6.

int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArraySum(nums));
// Output: 6

Example 2: Array with All Negative Numbers

When every element is negative, the best a contiguous subarray can do is pick the single least-negative element. For [-8, -3, -6, -2, -5, -4], that element is -2.

int[] nums = {-8, -3, -6, -2, -5, -4};
System.out.println(maxSubArraySum(nums));
// Output: -2

Common Mistakes to Avoid

Kadane’s Algorithm looks simple, but a few small missteps quietly change what problem it is solving. Watch for these specific mistakes.

• Clamping the running sum at zero – writing maxEndingHere = Math.max(0, maxEndingHere + nums[i]) solves a different problem that allows an empty subarray, and it silently returns 0 for an all-negative array instead of the correct least-negative answer. Drop the 0 floor and compare against nums[i] instead.
• Initializing both variables to 0 – seeding maxEndingHere and maxSoFar with 0 instead of nums[0] produces wrong answers whenever every element is negative, because 0 beats any negative sum. Seed both variables with nums[0] before the loop starts.
• Starting the loop at index 0 – looping from i = 0 redundantly recomputes the first element against itself. Start at i = 1, since nums[0] already seeded both running variables.
• Returning maxEndingHere instead of maxSoFar – the running sum at the final index is only the best subarray ending at the last position, not the global best. Always return maxSoFar.

Edge Cases to Test

A candidate who walks through these inputs unprompted demonstrates the kind of rigor interviewers are looking for.

• Empty array
• Null array reference
• Single-element array
• All negative elements
• All positive elements
• Maximum subarray at the very start of the array
• Maximum subarray at the very end of the array
• Integer.MIN_VALUE or Integer.MAX_VALUE present among the elements

Additional Considerations

Kadane’s Algorithm runs in O(n) time, visiting each element exactly once, and uses O(1) extra space, since maxEndingHere and maxSoFar are the only state carried between iterations. This makes it a textbook example of turning an O(n^2) brute-force scan into a single pass by recognizing the optimal-substructure relationship between a subarray and the one ending just before it.

The null and empty checks matter because an undefined input should never silently produce a number; throwing IllegalArgumentException surfaces the problem at the call site rather than letting a caller trust a meaningless result. Similarly, if the array can contain values near Integer.MIN_VALUE or Integer.MAX_VALUE, repeated additions inside the loop can overflow a 32-bit int; using a long accumulator removes that risk when the input range is not already constrained.

Although the loop never mentions a dynamic programming table, maxEndingHere is itself a one-dimensional DP state compressed to a single rolling variable: it always equals the best subarray sum ending at the current index, computed purely from the previous index’s value.

Interview Follow-up Questions

Once the base solution is working, interviewers typically probe how well you understand the underlying recurrence by changing the constraints.

• What if you need the actual subarray, not just its sum? – track candidate start and end indices alongside maxEndingHere, resetting the start whenever the algorithm restarts at the current element, and copying it into the recorded best indices whenever maxSoFar updates.
• What if the subarray is allowed to wrap around the end of the array back to the start? – the answer is the larger of the standard Kadane result and totalSum minus the minimum subarray sum, where the minimum is found by running the same recurrence with the comparisons flipped.
• What if you need the top K distinct maximum subarray sums instead of just the single best one? – a single rolling pair of variables is no longer enough; this generalizes to a divide-and-conquer or heap-based approach with higher time complexity.
• What if the array arrives as a stream of unknown length and cannot be stored in memory? – maintain maxEndingHere and maxSoFar incrementally as each new value arrives; the recurrence is identical, and termination comes from the end of the stream rather than an array length, so memory stays O(1) regardless of how many elements are processed.

Conclusion

Kadane’s Algorithm turns the maximum subarray sum problem from an O(n^2) brute-force scan into a single O(n) pass by tracking just two running values: the best sum ending at the current position, and the best sum seen anywhere so far. Once that recurrence clicks, the edge cases, the trace, and the follow-up variants all fall out of the same idea.

Try adapting the code to return the subarray indices, or to handle a circular array, using the follow-up hints above as a starting point. You can explore more array-based algorithms and interview-style walkthroughs in the Arrays category on this blog.