Kadane's Algorithm Explained: Maximum Subarray Sum in O(N)

If you pick up any textbook on Data Structures and Algorithms or look at the interview prep list for any FAANG company, you will inevitably encounter this problem:

"Given an array of integers (both positive and negative), find the contiguous subarray with the maximum sum."

The brute force approach—calculating the sum of every possible subarray—takes $O(N^2)$ or even $O(N^3)$ time. For an array of 100,000 elements, your program will time out.

Enter Kadane’s Algorithm—a beautiful, elegant dynamic programming technique that solves this problem in a single pass, in $O(N)$ time and $O(1)$ space.

Here is how it works.

The Intuition: The "Fresh Start" Principle

To understand Kadane's, you have to shift how you think about arrays. Stop trying to find the start and end of the subarray. Instead, ask yourself a simple question as you walk through the array element by element:

"Should I add this current element to my existing running sum, or should I start a brand new subarray from this element?"

Let’s look at an array: [1, -3, 2, 1, -1]

1. You start with 1. Your running sum is 1.
2. You hit -3. Your running sum drops to -2.
3. You hit 2. If you add it to your running sum (-2 + 2 = 0), you get 0. But if you just start fresh at 2, you get 2. Starting fresh is better.

The Golden Rule of Kadane's: If your running sum ever drops below zero, it becomes dead weight. It will only drag down any future positive numbers. Drop it like a bad habit and start a new subarray at the current element.

flowchart TD
    A[Initialize current_max and global_max]
    B[Read next element]
    C[Choose max of current element or extend previous sum]
    D[Update global maximum]
    E[Return answer]

    A --> B
    B --> C
    C --> D
    D --> B
    B -->|Finished| E

    style C fill:#4CAF50,color:#fff
    style D fill:#2196F3,color:#fff

The Algorithm in Code

The code is incredibly short, which makes it easy to memorize but easy to mess up if you don't understand the intuition.

def max_subarray_sum(nums):
    # Edge case: empty array
    if not nums:
        return 0

    # Initialize both variables to the first element.
    # (Do NOT initialize to 0, because the array might be all negative!)
    current_max = nums[0]
    global_max = nums[0]

    # Start iterating from the second element (index 1)
    for i in range(1, len(nums)):
        num = nums[i]

        # Step 1: Decide to extend the previous subarray or start fresh
        current_max = max(num, current_max + num)

        # Step 2: Update the overall maximum found so far
        global_max = max(global_max, current_max)

    return global_max

# Example Usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # Output: 6 (from subarray [4, -1, 2, 1])

The Biggest Trap: All Negative Arrays

Why do we initialize current_max and global_max to nums[0] instead of 0?

Imagine the array is [-5, -2, -9]. If you initialized to 0, the logic max(num, current_max + num) would evaluate max(-5, 0 + -5), which is -5. But what if your algorithm resets it to 0? The maximum sum would incorrectly be reported as 0 (an empty subarray).

By initializing to the first element, we guarantee we are always selecting at least one element, and the correct answer for [-5, -2, -9] will be -2.

Walkthrough: Visualizing the State

Let's trace Kadane's algorithm on the classic array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The global maximum locks in at 6, which corresponds to the subarray [4, -1, 2, 1].

Bonus: Finding the Actual Subarray

Interviewers love to follow up: "Can you return the actual subarray, not just the sum?"

We can do this by tracking the start and end indices whenever we update our current_max and global_max.

def get_max_subarray(nums):
    if not nums:
        return []

    current_max = global_max = nums[0]
    start = end = temp_start = 0

    for i in range(1, len(nums)):
        num = nums[i]

        # If starting fresh is better, reset the temp start pointer
        if num > current_max + num:
            current_max = num
            temp_start = i
        else:
            current_max += num

        # If we found a new global max, lock in the start and end pointers
        if current_max > global_max:
            global_max = current_max
            start = temp_start
            end = i

    return nums[start:end + 1]

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(get_max_subarray(arr))  # Output: [4, -1, 2, 1]

Complexity Analysis

• Time Complexity: $O(N)$. We only iterate through the array exactly once. No nested loops.
• Space Complexity: $O(1)$. We only use two variables (current_max and global_max) regardless of the array size. (Or a few extra integers if tracking indices).

Conclusion

Kadane’s algorithm is a masterclass in dynamic programming. It takes a problem that seems to require examining $N^2$ combinations and solves it by maintaining a single piece of state: Is my past baggage helping me, or hurting me?

Memorize the logic—max(num, current_max + num)—understand why we don't initialize to zero, and you will never fail this question in an interview again.