Maximum Subarray Algorithm: Kadane's Guide & Code Examples

Imagine you're analyzing stock prices over the past month, trying to find the best continuous period to buy and sell. You want the stretch of days that maximizes your profit—not just any days, but a consecutive run. This is the maximum subarray algorithm in action, a classic problem in dynamic programming that shows up everywhere from financial analysis to genomics.

I've lost count of how many times this problem has appeared in coding interviews over my 15 years as a software engineer. It's one of those questions that separates candidates who memorize solutions from those who truly understand algorithmic thinking. In this guide, I'll walk you through everything—from the naive brute-force approaches to Kadane's elegant O(n) solution, plus the divide and conquer alternative and real-world applications you might not have considered.

---

What is the Maximum Subarray Problem? Definition & Core Concepts

The maximum subarray problem asks a deceptively simple question: given an array of integers (which can include negative numbers), find the contiguous subarray with the largest sum.

Let's make this concrete. Consider the array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum subarray is [4, -1, 2, 1], which sums to 6. Notice something interesting—the subarray includes a negative number (-1) because dropping it would mean also dropping the positive numbers around it. That's the crux of the problem: you can't cherry-pick elements; they must be contiguous.

Subarray vs. Subsequence: A Critical Distinction

Before we dive deeper, let's clear up a confusion that trips up many beginners.

A subarray is a contiguous segment of an array. For [1, 2, 3, 4], the subarrays include [1, 2], [2, 3, 4], and [3]—but not [1, 3] because those elements aren't adjacent.

A subsequence, on the other hand, maintains the original order but doesn't require contiguity. So [1, 3, 4] is a valid subsequence of [1, 2, 3, 4], but not a subarray.

Array:    [1,  2,  3,  4]
Subarray: [1,  2]  ✓  (contiguous)
Subsequence: [1,  3,  4]  ✓  (order preserved, not contiguous)

Why does this matter? Because the maximum subarray algorithm specifically targets contiguous segments. If you were allowed to skip elements, the solution would be trivial—just sum all the positive numbers. The contiguity constraint is what makes this problem interesting and genuinely useful for real-world scenarios where "continuous" matters.

Formal Definition and Mathematical Notation

For the mathematically inclined, here's the formal statement:

Given an array arr of length n, find:

max(arr[i] + arr[i+1] + ... + arr[j])  where  0 ≤ i ≤ j < n

In other words, we're maximizing the sum of a contiguous segment arr[i...j]. The array can contain negative numbers, which is what makes the problem non-trivial. If all elements were positive, the answer would simply be the sum of the entire array.

---

Brute Force Solutions: From O(n³) to O(n²)

Let's start with the most intuitive approach—the one I'd expect any candidate to mention first in an interview.

The O(n³) approach: Generate every possible subarray, calculate each sum, and track the maximum. For an array of length n, there are n(n+1)/2 subarrays. For each one, we compute the sum by iterating through its elements.

def max_subarray_brute_force(arr):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = 0
            for k in range(i, j + 1):
                current_sum += arr[k]
            max_sum = max(max_sum, current_sum)
    return max_sum

This works, but it's painfully slow. For an array of 10,000 elements, we're talking about billions of operations. In my early days, I made the mistake of using this approach on a moderately sized dataset and watched my program crawl to a halt.

The O(n²) optimization: Here's a simple insight that cuts the time complexity down a notch. Instead of recalculating the sum from scratch for each subarray, we can build incrementally:

def max_subarray_on2(arr):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]
            max_sum = max(max_sum, current_sum)
    return max_sum

The key realization: when we extend a subarray from arr[i...j-1] to arr[i...j], we just add arr[j] to the previous sum. No need to re-add everything.

Both approaches are correct, but they're not practical for large inputs. The brute force solutions are valuable primarily as a baseline—they help you verify that your optimized solution produces correct results.

---

Kadane's Algorithm: The Optimal O(n) Dynamic Programming Solution

Now we get to the star of the show. Kadane's algorithm is the elegant, linear-time solution that makes this problem a favorite in coding interviews. It's named after Jay Kadane, who proposed it in 1984, though the underlying idea had been around for a while.

How Kadane's Algorithm Works: A Step-by-Step Walkthrough

The core intuition is deceptively simple: at each position in the array, we maintain two values:

1. Local maximum: the maximum subarray sum ending at the current position
2. Global maximum: the maximum subarray sum we've seen so far

Here's the key decision at each step: should we extend the previous subarray, or start fresh at the current element?

local_max[i] = max(arr[i], local_max[i-1] + arr[i])

If local_max[i-1] is negative, adding it to arr[i] only makes things worse. In that case, we're better off starting a new subarray at arr[i].

Let's walk through our example array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

One edge case worth noting: what if all numbers are negative? The algorithm still works correctly—it will simply pick the largest (least negative) element. For [-5, -2, -8, -1], the maximum subarray sum is -1, which is just the single element [-1].

Correctness Proof and Intuition

You might be wondering: how do we know this simple approach always works? Let me walk you through the reasoning.

The proof relies on induction. We claim that after processing index i, local_max[i] correctly represents the maximum sum of any subarray ending at index i.

Base case: For i = 0, the only subarray ending at index 0 is [arr[0]], so local_max[0] = arr[0] is correct.

Inductive step: Assume local_max[i-1] is correct. Consider any subarray ending at index i. It either:

• Starts at index i (just [arr[i]]), or
• Extends a subarray ending at index i-1

In the second case, the maximum sum would be local_max[i-1] + arr[i]. Since we take the maximum of these two possibilities, local_max[i] is correct.

This connects directly to the principle of optimality in dynamic programming: the optimal solution to a problem can be constructed from optimal solutions to its subproblems. Here, the optimal subarray ending at i depends only on the optimal subarray ending at i-1—we don't need to consider any other subarrays ending at i-1.

Time and Space Complexity Analysis

Here's where Kadane's algorithm really shines:

---

Maximum Subarray Divide and Conquer: A Comparative Analysis

While Kadane's algorithm is the go-to solution, the maximum subarray divide and conquer approach deserves attention—both for its elegance and because it's a common interview follow-up question.

How the Divide and Conquer Approach Works

The idea is to recursively split the array in half and consider three cases:

1. The maximum subarray lies entirely in the left half
2. The maximum subarray lies entirely in the right half
3. The maximum subarray crosses the midpoint

Cases 1 and 2 are handled recursively. Case 3 requires a separate merge step: we find the maximum suffix sum of the left half and the maximum prefix sum of the right half, then add them together.

Array: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
                    ↑
                 midpoint

Left half:  [-2, 1, -3, 4]
Right half: [-1, 2, 1, -5, 4]

Case 1: Max subarray in left half → [4] (sum = 4)
Case 2: Max subarray in right half → [2, 1] (sum = 3)
Case 3: Crossing subarray → [4, -1, 2, 1] (sum = 6) ← winner

The crossing case requires finding the maximum sum that extends from the midpoint to the left and from the midpoint+1 to the right. This takes O(n) time at each level of recursion.

Here's the pseudocode:

function max_subarray_dc(arr, low, high):
    if low == high:
        return arr[low]
    
    mid = (low + high) / 2
    
    left_max = max_subarray_dc(arr, low, mid)
    right_max = max_subarray_dc(arr, mid + 1, high)
    cross_max = max_crossing_subarray(arr, low, mid, high)
    
    return max(left_max, right_max, cross_max)

Kadane's Algorithm vs. Divide and Conquer: Pros and Cons

That said, I've seen interviewers ask for the divide and conquer version specifically to test whether candidates understand recursion and the "merge" step. It's worth knowing both.

---

Maximum Subarray Sum Code Examples: Python, Java, and C++

Let's get practical. Here are clean implementations of Kadane's algorithm in three popular languages.

Python Implementation

def max_subarray_sum(arr):
    """
    Find the maximum subarray sum using Kadane's algorithm.
    Returns the maximum sum and the start/end indices of the subarray.
    """
    if not arr:
        return 0, -1, -1
    
    max_sum = arr[0]
    current_sum = arr[0]
    start = end = 0
    temp_start = 0
    
    for i in range(1, len(arr)):
        # Decide: extend previous subarray or start new one
        if arr[i] > current_sum + arr[i]:
            current_sum = arr[i]
            temp_start = i
        else:
            current_sum = current_sum + arr[i]
        
        # Update global maximum if needed
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i
    
    return max_sum, start, end

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result, start, end = max_subarray_sum(arr)
print(f"Array: {arr}")
print(f"Maximum subarray sum: {result}")
print(f"Subarray: {arr[start:end+1]} (indices {start} to {end})")

Output:

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Maximum subarray sum: 6
Subarray: [4, -1, 2, 1] (indices 3 to 6)

Java Implementation

public class MaxSubarray {
    
    public static int[] maxSubarraySum(int[] arr) {
        if (arr.length == 0) {
            return new int[]{0, -1, -1};
        }
        
        int maxSum = arr[0];
        int currentSum = arr[0];
        int start = 0, end = 0, tempStart = 0;
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > currentSum + arr[i]) {
                currentSum = arr[i];
                tempStart = i;
            } else {
                currentSum = currentSum + arr[i];
            }
            
            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }
        }
        
        return new int[]{maxSum, start, end};
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] result = maxSubarraySum(arr);
        
        System.out.print("Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        System.out.println("Maximum subarray sum: " + result[0]);
        System.out.print("Subarray: ");
        for (int i = result[1]; i <= result[2]; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("(indices " + result[1] + " to " + result[2] + ")");
    }
}

C++ Implementation

#include <iostream>
#include <vector>
#include <tuple>

std::tuple<int, int, int> maxSubarraySum(const std::vector<int>& arr) {
    if (arr.empty()) {
        return {0, -1, -1};
    }
    
    int maxSum = arr[0];
    int currentSum = arr[0];
    int start = 0, end = 0, tempStart = 0;
    
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > currentSum + arr[i]) {
            currentSum = arr[i];
            tempStart = i;
        } else {
            currentSum = currentSum + arr[i];
        }
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
    }
    
    return {maxSum, start, end};
}

int main() {
    std::vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    auto [maxSum, start, end] = maxSubarraySum(arr);
    
    std::cout << "Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    std::cout << "Maximum subarray sum: " << maxSum << std::endl;
    std::cout << "Subarray: ";
    for (int i = start; i <= end; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << "(indices " << start << " to " << end << ")" << std::endl;
    
    return 0;
}

One thing I've learned from years of code reviews: the version that returns indices is what most interviewers actually want to see. It shows you understand not just the algorithm, but also how to track state through the iteration.

---

Beyond the Basics: Variations and Real-World Applications

The maximum subarray algorithm isn't just an academic exercise. Once you understand the core pattern, you'll start seeing it everywhere.

Variations: Maximum Circular Subarray Sum and Maximum Submatrix Sum

Maximum Circular Subarray Sum: What if the array wraps around? In other words, the subarray can span from the end of the array back to the beginning. The solution uses a clever trick: the maximum circular subarray sum is either the regular maximum subarray sum, or the total sum minus the minimum subarray sum. This is the approach for LeetCode 918.

Maximum Submatrix Sum (2D version): This is where things get interesting. Given a 2D matrix, find the submatrix with the largest sum. The trick is to collapse rows: for each pair of rows, compute the column-wise sums, then run Kadane's algorithm on the resulting 1D array. This reduces the 2D problem to a series of 1D problems.

Maximum Product Subarray: Similar to the sum version, but with multiplication. The twist is that a negative product can become positive when multiplied by another negative number, so you need to track both the maximum and minimum products ending at each position.

Real-World Use Cases: From Finance to Genomics

Stock Price Analysis: This is the classic application I mentioned in the introduction. Given daily price changes, find the continuous period that maximizes profit. The maximum subarray algorithm directly solves this.

Genomics: In DNA sequence analysis, researchers look for regions with high similarity between sequences. The Smith-Waterman algorithm, used for local sequence alignment, is essentially a variation of the maximum subarray problem applied to a 2D scoring matrix.

Image Processing: Finding the brightest region in an image can be framed as a maximum submatrix problem. Each pixel's intensity becomes an element in the matrix, and the algorithm identifies the contiguous region with the highest total intensity.

Signal Processing: When analyzing sensor data, the maximum subarray algorithm can identify periods of unusual activity—like a spike in network traffic or an anomaly in a machine's vibration pattern.

---

Mastering the Maximum Subarray Algorithm for Coding Interviews

If you're preparing for technical interviews, this algorithm is non-negotiable. I've seen it appear at companies ranging from startups to FAANG, and it's often the first question in a series of follow-ups.

Common Interview Questions and Variations

Here are the problems I'd recommend practicing:

• LeetCode 53: Maximum Subarray — The classic. You should be able to solve this in your sleep.
• LeetCode 918: Maximum Sum Circular Subarray — Tests whether you truly understand the algorithm's mechanics.
• LeetCode 152: Maximum Product Subarray — A common follow-up that requires adapting the approach.
• Return the subarray, not just the sum — Many candidates can find the sum but struggle with tracking indices.
• Handle edge cases — All negative numbers, empty array, single element.

Tips for Explaining Your Solution in an Interview

Based on my experience both as an interviewer and as a candidate, here's what works:

Start with brute force. Even if you know the optimal solution immediately, walk through the naive approach first. It shows you understand the problem deeply and can reason from first principles.

Articulate the intuition clearly. Don't just recite the formula. Explain why it works: "At each position, I'm asking whether extending the previous subarray helps or hurts. If the previous subarray sum is negative, it's better to start fresh."

Discuss complexity without being asked. Mention that Kadane's runs in O(n) time and O(1) space, and be ready to explain why that's optimal.

Practice on a whiteboard. The algorithm is simple enough to implement by hand, but the pressure of an interview can make you forget basic syntax. Practice writing it out without an IDE.

Be ready for follow-ups. Interviewers love to ask: "What if the array is circular?" or "What if we need the actual subarray?" Have these variations prepared.

---

Frequently Asked Questions

What is the maximum subarray algorithm?

The maximum subarray algorithm is a dynamic programming technique used to find the contiguous subarray within a one-dimensional array that has the largest sum. The most efficient implementation is Kadane's algorithm, which solves the problem in O(n) time by maintaining a running local maximum and a global maximum as it traverses the array.

How does Kadane's algorithm work?

Kadane's algorithm works by iterating through the array once, maintaining two values: the maximum subarray sum ending at the current position (local maximum) and the maximum subarray sum seen so far (global maximum). At each step, it decides whether to extend the previous subarray or start a new one at the current element, based on which option yields a larger sum.

What is the time complexity of the maximum subarray problem?

The optimal solution using Kadane's algorithm runs in O(n) time with O(1) space. Brute force approaches range from O(n²) to O(n³), while the divide and conquer approach runs in O(n log n) time.

Can the maximum subarray problem be solved using divide and conquer?

Yes. The divide and conquer approach splits the array in half and considers three cases: the maximum subarray is entirely in the left half, entirely in the right half, or crosses the midpoint. It runs in O(n log n) time, which is slower than Kadane's algorithm but offers better parallelization potential.

What is the difference between maximum subarray and maximum subsequence?

A subarray must be contiguous—elements must be adjacent in the original array. A subsequence only needs to preserve the original order, but elements can be non-contiguous. The maximum subarray algorithm specifically targets contiguous segments, which is what makes the problem non-trivial.

---

Conclusion

We've come a long way from the brute force O(n³) approach to Kadane's elegant O(n) solution. The maximum subarray algorithm is more than just an interview question—it's a gateway to understanding dynamic programming, algorithmic optimization, and how to think about problems where the naive solution isn't good enough.

What I appreciate most about this algorithm is how it embodies a fundamental principle: sometimes the best way to solve a problem is to break it into smaller pieces and build up the solution incrementally. That's a mindset that applies far beyond coding.

Ready to test your skills? Head over to LeetCode and try solving "Maximum Subarray" (Problem 53) and its variations. Don't forget to check out our other algorithm guides for more interview prep!