Mastering the Maximum Subarray: Kadane’s Algorithm Guide

Introduction to the Maximum Subarray Problem

When preparing for technical interviews at top-tier tech companies like Google, Meta, Amazon, or Netflix, you will inevitably run into a set of classic algorithmic challenges. Among these, the Maximum Subarray problem (LeetCode 53) stands out as a rite of passage. It is one of the most frequently asked questions because it perfectly tests a candidate's ability to transition from a naive, brute-force mindset to an optimized, highly efficient dynamic programming mindset.

At first glance, finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum seems simple. However, when you factor in negative numbers, the problem becomes a fascinating exercise in optimization. How do you decide whether to include a negative number in your current run, or to discard the progress you have made so far and start fresh?

In this comprehensive guide, we will break down the problem in plain, human-friendly English. We will explore the naive approaches, deep-dive into the intuition behind the legendary Kadane's Algorithm, and provide highly optimized, production-ready solutions in 11 different programming languages. By the end of this masterclass, you will not only write this algorithm effortlessly but also understand the core intuition behind it.

Understanding the Problem Statement

Before we jump into any code, let's make sure we completely understand what the problem is asking. The problem statement is typically written as follows:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Let's unpack the key terms here:

• Contiguous: This means the elements must be adjacent to each other in the array. You cannot skip elements. For example, in the array [1, 2, -3, 4], the subset [1, 2] is contiguous, but [1, 4] is not.

• Subarray: A portion of an array. It can be as small as a single element or as large as the entire array itself.

• Largest Sum: We want to find the collection of contiguous elements that, when added together, produce the highest possible value.

A Real-World Analogy

Imagine you are walking down a straight street lined with shops. Some shops are giving out cash (positive numbers), while others require you to pay an entry fee (negative numbers). Your goal is to choose a continuous stretch of shops to visit that maximizes the net money in your pocket. If you hit a long stretch of expensive shops that drains all your cash, it might be smarter to stop your current run, walk past them, and start a brand-new run at a later shop. This is the exact intuition we will use to build our optimal solution!

The Naive Approach: Brute Force

To understand why the optimal solution is so elegant, we must first look at the slow way of solving this problem. The most straightforward approach is to calculate the sum of every possible contiguous subarray and keep track of the maximum sum we find.

To do this, we would use nested loops:

1. The outer loop selects the starting index of our subarray.

2. The inner loop selects the ending index and calculates the sum of that specific range.

3. We compare this sum to our running maximum and update it if the new sum is larger.

While this is simple to write, it requires O(N²) time complexity, where N is the length of the array. If the array has 100,000 elements, an O(N²) solution would require around 10 billion operations, resulting in a "Time Limit Exceeded" (TLE) error on LeetCode. We need a faster way.

The Breakthrough: Kadane's Algorithm

In 1984, Jay Kadane of Carnegie Mellon University designed an incredibly elegant O(N) time complexity algorithm to solve this problem in a single pass. The beauty of Kadane's Algorithm lies in its simplicity. It relies on a simple, yet profound, decision-making rule at each step of our array traversal.

As we iterate through the array from left to right, we maintain two variables:

• current_sum: The maximum sum of the subarray ending at the current position.

• global_max: The overall maximum sum we have seen so far across the entire array.

The Core Decision Rule

When we are at any element nums[i], we have to make a choice. Should we add nums[i] to our existing current_sum, or should we throw away our existing run and start a brand-new subarray beginning at nums[i]?

Mathematically, the choice is simple:

current_sum = max(nums[i], current_sum + nums[i])

If our existing current_sum has become negative, adding it to nums[i] will only drag the value of nums[i] down. Therefore, whenever our previous run is doing more harm than good, we abandon it and restart our sum from the current element. Once we update current_sum, we update our global_max if the new current_sum is larger:

global_max = max(global_max, current_sum)

By making this local decision at every index, we guarantee that we find the global optimum in a single scan of the array.

Optimal Solutions in Every LeetCode-Accepted Language

Here are the clean, optimized, production-ready implementations of Kadane's Algorithm in all major languages accepted by LeetCode. Every solution runs in O(N) time complexity and O(1) space complexity.

1. Python

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        global_max = nums[0]
        current_sum = nums[0]
        
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            global_max = max(global_max, current_sum)
            
        return global_max

2. Java

class Solution {
    public int maxSubArray(int[] nums) {
        int globalMax = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            globalMax = Math.max(globalMax, currentSum);
        }
        
        return globalMax;
    }
}

3. C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        int globalMax = nums[0];
        int currentSum = nums[0];
        
        for (size_t i = 1; i < nums.size(); ++i) {
            currentSum = std::max(nums[i], currentSum + nums[i]);
            globalMax = std::max(globalMax, currentSum);
        }
        
        return globalMax;
    }
};

4. JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let globalMax = nums[0];
    let currentSum = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        globalMax = Math.max(globalMax, currentSum);
    }
    
    return globalMax;
};

5. TypeScript

function maxSubArray(nums: number[]): number {
    let globalMax: number = nums[0];
    let currentSum: number = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        globalMax = Math.max(globalMax, currentSum);
    }
    
    return globalMax;
}

6. C#

using System;

public class Solution {
    public int MaxSubArray(int[] nums) {
        int globalMax = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            globalMax = Math.Max(globalMax, currentSum);
        }
        
        return globalMax;
    }
}

7. Go

func maxSubArray(nums []int) int {
    globalMax := nums[0]
    currentSum := nums[0]
    
    for i := 1; i < len(nums); i++ {
        if nums[i] > currentSum + nums[i] {
            currentSum = nums[i]
        } else {
            currentSum = currentSum + nums[i]
        }
        
        if currentSum > globalMax {
            globalMax = currentSum
        }
    }
    
    return globalMax
}

8. Rust

use std::cmp;

impl Solution {
    pub fn max_subarray(nums: Vec<i32>) -> i32 {
        let mut global_max = nums[0];
        let mut current_sum = nums[0];
        
        for &num in nums.iter().skip(1) {
            current_sum = cmp::max(num, current_sum + num);
            global_max = cmp::max(global_max, current_sum);
        }
        
        global_max
    }
}

9. Swift

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var globalMax = nums[0]
        var currentSum = nums[0]
        
        for i in 1..<nums.count {
            currentSum = max(nums[i], currentSum + nums[i])
            globalMax = max(globalMax, currentSum)
        }
        
        return globalMax
    }
}

10. Kotlin

import kotlin.math.max

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var globalMax = nums[0]
        var currentSum = nums[0]
        
        for (i in 1 until nums.size) {
            currentSum = max(nums[i], currentSum + nums[i])
            globalMax = max(globalMax, currentSum)
        }
        
        return globalMax
    }
}

11. Ruby

# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
    global_max = nums[0]
    current_sum = nums[0]
    
    (1...nums.length).each do |i|
        current_sum = [nums[i], current_sum + nums[i]].max
        global_max = [global_max, current_sum].max
    end
    
    global_max
end

Crucial Edge Cases & Interview Gotchas

During a technical interview, writing the correct code is only half the battle. To truly stand out, you must proactively identify and explain edge cases. Here are the main gotchas to watch out for in the Maximum Subarray problem:

• All Negative Numbers: If the input array is [-3, -1, -2], the output should be -1. Older implementations of Kadane's Algorithm sometimes initialized the global maximum to 0, which would incorrectly return 0 for this case. By initializing both variables to the first element of the array (nums[0]), our code safely handles entirely negative arrays.

• Single Element Arrays: If the input is [5], the loop will not execute, and the code will correctly return 5. Always make sure your loop indices do not throw out-of-bounds exceptions on short inputs.

• Integer Overflow: In some competitive programming environments, the sum of array values might exceed the limit of standard 32-bit signed integers. In standard LeetCode problems, this is rarely an issue, but it is always wise to ask your interviewer if you should use 64-bit integers (like long in Java/C++).

Complexity Analysis

Let's formally verify the performance of our solution:

• Time Complexity: O(N). We iterate through the array of length N exactly once. Inside the loop, we only perform basic constant-time additions and comparison operations.

• Space Complexity: O(1). We do not allocate any additional arrays or recursive call stacks. We only use two scalar variables to keep track of state, resulting in constant auxiliary memory.

Take Your Skills to the Next Level

Mastering array traversal and the dynamic state-tracking used in Kadane's Algorithm is a massive milestone for any software engineer. It builds the foundational patterns you need to tackle more advanced problems involving sliders, dynamic programming matrices, and two-pointer strategies.

Once you feel comfortable with the Maximum Subarray problem, you should continue building your muscle memory with other essential array algorithms. To continue your preparation journey, dive into our step-by-step masterclass on Mastering Remove Duplicates from Sorted Array. Expanding your toolkit with these highly frequent array manipulation patterns is the most reliable way to build confidence and ace your upcoming technical interviews.