Kadane's Algorithm: Core Logic Explained

Welcome to the next lesson in our exploration of array algorithms. In our last session, we mastered a powerful pattern combining prefix sums and hash maps to count subarrays with a specific target sum. We saw how a clever algebraic trick could transform an $O(N^2)$ problem into a linear-time solution.

Today, we shift our focus from finding a specific sum to finding the greatest sum. This lesson addresses the learning outcome: Explain the core logic of Kadane's algorithm for the maximum subarray problem. This is a classic and elegant algorithm that every computer scientist should know, not just for its efficiency but for its beautifully simple and powerful core idea. Your interest in finance might find a parallel here: this problem is analogous to finding the most profitable period to trade a stock if you were given a list of its daily price changes.

The Maximum Subarray Problem

The problem is straightforward: given an array of integers (which can be positive, negative, or zero), find the contiguous subarray that has the largest possible sum.

For example, in the array [4, -1, 2, 1], the maximum subarray sum is 6 (from the subarray [4, -1, 2, 1]). In [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum sum is 6 (from [4, -1, 2, 1]).

How would we approach this? As you know from your LeetCode experience, a good starting point is to consider the brute-force solution. We could generate every single possible contiguous subarray, calculate the sum of each, and keep track of the maximum sum we find.

The following video from NeetCode quickly walks through why this approach, while correct, is too slow for typical constraints.

An $O(N^2)$ solution is a good start, but we can do better. We can solve this problem in a single pass, using $O(N)$ time. This is where Kadane's algorithm comes in.

The Core Insight: Discarding Negative Prefixes

The genius of Kadane's algorithm lies in a single, simple observation. As we iterate through the array, we build a current_sum. Let's say we are at index i, and the sum of the subarray ending at i-1 has become negative.

Now, consider extending this subarray to include the element at index i. The new sum will be (negative_sum) + nums[i], which is guaranteed to be less than just nums[i] by itself.

This means a subarray with a negative sum is "toxic"—it will only decrease the sum of any future subarray that tries to include it. Therefore, whenever our current_sum dips below zero, it's more advantageous to discard that entire prefix and start a fresh subarray from the current element.

This gives us the core logic:

1. Maintain a current_sum for the subarray ending at the current position.
2. Maintain a max_so_far to track the best sum found anywhere in the array.
3. As you iterate through the array, add the current element to current_sum.
4. After updating current_sum, compare it with max_so_far and update max_so_far if current_sum is larger.
5. Crucially: If current_sum ever becomes negative, reset it to 0. This is the "discarding" step. By resetting to zero, we are effectively deciding to start a new subarray from the next element.

The following video from take U forward provides an excellent, detailed walkthrough of this exact thought process.

This simple set of rules is the entirety of Kadane's algorithm. It's an elegant example of a greedy approach. At each step, we make the locally optimal choice (do we extend the current subarray or start a new one?), and this leads to the globally optimal solution.

A Step-by-Step Walkthrough

Let's trace the algorithm on the array nums = [-2, -3, 4, -1, -2, 1, 5, -3]. We'll use two variables: current_sum (initialized to 0) and max_sum (initialized to a very small number, like $-\infty$, to correctly handle all-negative arrays).

The image below shows the state of these variables at each step.

Let's follow the logic as depicted in the table:

1. Initial State: current_sum = 0, max_sum = -∞.
2. i=0 (num = -2):
   • current_sum becomes 0 + (-2) = -2.
   • max_sum is updated to max(-∞, -2), which is -2.
   • current_sum is negative, so we reset it to 0 for the next iteration.
3. i=1 (num = -3):
   • current_sum becomes 0 + (-3) = -3.
   • max_sum remains -2 (max(-2, -3) is -2).
   • current_sum is negative, so reset to 0.
4. i=2 (num = 4):
   • current_sum becomes 0 + 4 = 4.
   • max_sum is updated to max(-2, 4), which is 4.
   • current_sum is positive, so we keep it.
5. i=3 (num = -1):
   • current_sum becomes 4 + (-1) = 3.
   • max_sum remains 4.
   • current_sum is positive, so we keep it.
6. i=4 (num = -2):
   • current_sum becomes 3 + (-2) = 1.
   • max_sum remains 4.
   • current_sum is positive, so we keep it.
7. i=5 (num = 1):
   • current_sum becomes 1 + 1 = 2.
   • max_sum remains 4.
   • current_sum is positive, so we keep it.
8. i=6 (num = 5):
   • current_sum becomes 2 + 5 = 7.
   • max_sum is updated to max(4, 7), which is 7.
   • current_sum is positive, so we keep it.
9. i=7 (num = -3):
   • current_sum becomes 7 + (-3) = 4.
   • max_sum remains 7.
   • The loop ends.

The final answer is 7. The subarray that produces this sum is [4, -1, -2, 1, 5].

The Dynamic Programming Perspective

Kadane's algorithm can also be framed as a simple dynamic programming problem. Let dp[i] be the maximum subarray sum ending at index i. To compute dp[i], we have two choices:

1. Start a new subarray at index i. The sum would simply be nums[i].
2. Extend the maximum subarray that ended at index i-1 by adding nums[i]. The sum would be dp[i-1] + nums[i].

We choose whichever is larger. This gives us the recurrence relation:
$dp[i]=\max (nums[i],dp[i-1]+nums[i])$

The current_sum in our greedy approach is exactly this dp[i]. If dp[i-1] (the previous current_sum) was negative, then nums[i] will always be greater than dp[i-1] + nums[i], which is the same as our "reset to 0" logic (if you consider the sum before adding nums[i]). The overall maximum subarray sum is then the maximum value found in our dp array (or our max_so_far variable).

A Note on Edge Cases

What happens if the array contains only negative numbers, like [-5, -2, -3]?
Our logic says to reset current_sum to 0 whenever it becomes negative. If max_sum were initialized to 0, we would incorrectly return 0. However, the problem states we must find a non-empty subarray. The correct answer should be -2.

This highlights the importance of correctly initializing max_sum. By setting it to the first element of the array or negative infinity, we ensure that the algorithm correctly finds the "least negative" number in an all-negative array. We will dive deeper into this and other implementation details in our next lesson.

For now, focus on the core logic. This guide summarizes it well.

Conclusion

In this lesson, we've unpacked the simple yet powerful logic behind Kadane's algorithm. You've moved from brute-force thinking to a linear-time, greedy approach for solving the maximum subarray problem.

Key Takeaways:

• The Problem: Find the contiguous subarray within an array that has the largest sum.
• The Core Logic: A running sum (prefix) that becomes negative is detrimental to any future subarray. It's always better to discard it and start a new subarray.
• The Algorithm: Iterate through the array with a current_sum and a max_sum. At each step, add the element to current_sum, update max_sum, and if current_sum drops below zero, reset it to zero.
• Efficiency: This elegant approach solves the problem in $O(N)$ time and $O(1)$ space.

In our next lesson, we will build on this understanding. We'll implement Kadane's algorithm, paying close attention to the critical details of initialization and handling edge cases like all-negative arrays. We'll also explore how to adapt the algorithm to not just return the sum, but also the start and end indices of the maximum subarray itself.