Kadane's Algorithm: Mastering Maximum Subarray Sum

In our previous lesson, we explored the elegant core logic of Kadane's algorithm, understanding why discarding a subarray with a negative sum is the key to finding the maximum possible sum. This "greedy" choice at each step simplifies what seems like a complex problem into a single, efficient pass.

Now, we will transition from the conceptual to the practical. This lesson focuses on the learning outcome: Implement Kadane's algorithm, handling edge cases such as all-negative arrays. Translating an algorithm's logic into robust code requires careful attention to detail, especially regarding initialization and boundary conditions. Mastering this is a critical skill for producing correct and reliable solutions, something highly valued in coding interviews and professional practice.

From Logic to Implementation

Let's start by formalizing the algorithm we discussed. At its heart, it involves two main variables:

1. A current_sum to track the maximum sum of a subarray ending at the current position.
2. A max_sum to store the overall maximum sum found anywhere in the array so far.

The process is as follows:

• Initialize current_sum and max_sum.
• Iterate through the array, element by element.
• For each element, update current_sum.
• Then, update max_sum by comparing it with the new current_sum.
• Return max_sum after the loop.

The crucial detail lies in the initialization and update rules. Let's examine the most common pitfall.

The All-Negative Array Edge Case

Consider an array where all numbers are negative, like [-5, -2, -3]. The problem asks for the sum of a non-empty contiguous subarray. In this case, the subarray with the largest sum is simply [-2], and the answer should be -2.

What happens if we initialize max_sum = 0 and current_sum = 0?

1. Start: max_sum = 0, current_sum = 0.
2. Element -5: current_sum becomes -5. max_sum is max(0, -5), which is 0. We then reset current_sum to 0 because it's negative.
3. Element -2: current_sum becomes -2. max_sum is max(0, -2), which is 0. Reset current_sum to 0.
4. Element -3: current_sum becomes -3. max_sum is max(0, -3), which is 0. Reset current_sum to 0.

The final answer would be 0, which is incorrect. This common mistake is highlighted in the following guide.

As the article states, the solution is to initialize max_sum to a value that is guaranteed to be less than or equal to any possible correct answer. There are two standard, robust ways to do this.

Strategy 1: Initialize with Negative Infinity

The most common and arguably cleanest approach is to initialize max_sum to the smallest possible number (negative infinity). This ensures that the sum of the very first element (or any valid subarray sum) will be greater, correctly setting our baseline. current_sum can start at 0.

The following resource provides code examples demonstrating this exact strategy.

Let's trace this implementation with nums = [-5, -2, -3]:

• Initial: max_sum = -∞, current_sum = 0.
• i=0 (num = -5):
  • current_sum becomes 0 + (-5) = -5.
  • max_sum becomes max(-∞, -5) = -5.
  • current_sum is negative, so reset to 0.
• i=1 (num = -2):
  • current_sum becomes 0 + (-2) = -2.
  • max_sum becomes max(-5, -2) = -2.
  • current_sum is negative, so reset to 0.
• i=2 (num = -3):
  • current_sum becomes 0 + (-3) = -3.
  • max_sum remains -2 (max(-2, -3) = -2).
  • current_sum is negative, so reset to 0.

The loop finishes, and we correctly return max_sum = -2.

Strategy 2: Initialize with the First Element

An alternative approach, which avoids using a special "infinity" value, is to initialize both max_sum and current_sum to the first element of the array, nums[0]. The loop then starts from the second element (nums[1]).

This works because any valid subarray must contain at least one element, so the maximum sum must be at least the largest single element in the array. By initializing with nums[0], we start with a valid candidate.

This leads to a slightly more compact implementation, which maps beautifully to the dynamic programming recurrence we touched on in the last lesson: $dp[i]=\max (nums[i],dp[i-1]+nums[i])$. Here, current_sum is our dp value.

The core of the loop becomes:
current_sum = max(current_element, current_sum + current_element)

This elegantly captures the decision: either start a new subarray with the current_element or extend the previous subarray.

You can see this implementation in the NeetCode video below.

Here is a Python implementation of this second flavor:

def max_subarray_sum(nums):
    if not nums:
        return 0 # Or handle as an error, depending on constraints
    



    # Initialize with the first element's value
    max_so_far = nums[0]
    current_max = nums[0]
    



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



        # Decide: extend the current subarray or start a new one?
        current_max = max(num, current_max + num)



        # Update the overall maximum found so far
        max_so_far = max(max_so_far, current_max)
        
    return max_so_far

Both strategies are correct and widely used. The second one is often favored in competitive programming for its conciseness.

A Note on Problem Constraints

In a coding interview, it's wise to clarify constraints. The standard "Maximum Subarray" problem (LeetCode 53) assumes the input array is non-empty. What if it could be empty? Or what if the problem statement specified that an empty subarray (with sum 0) is a valid choice?

This highlights a key takeaway: while the core algorithm is consistent, the final return value might need a small adjustment based on the exact problem statement. If an empty subarray with sum 0 is allowed, and your calculated max_sum is negative, you would return 0 instead.

Conclusion

You have now moved from the theory of Kadane's algorithm to its practical, robust implementation. You are equipped to write correct code that handles the crucial edge case of an all-negative array.

Key Takeaways:

• The Pitfall: Initializing max_sum to 0 will fail for arrays where the maximum subarray sum is negative.
• Strategy 1 (Reset Logic): Initialize max_sum to negative infinity and current_sum to 0. In the loop, if current_sum becomes negative, reset it to 0.
• Strategy 2 (DP Logic): Initialize max_sum and current_sum to nums[0]. In the loop (starting from index 1), update current_sum using max(num, current_sum + num).
• Interview Practice: Always clarify constraints, such as whether the input can be empty or if an empty subarray (sum 0) is a valid answer.

In our next lesson, we will tackle a common follow-up question: how to adapt Kadane's algorithm to track the start and end indices of the maximum subarray, not just its sum. This will complete your mastery of this fundamental algorithm pattern.