Maximum Subarray Sum (Kadane’s Algorithm)

Introduction

Imagine you’re tracking your daily profits and losses, and you want to find the best consecutive period that maximizes your total gain. That’s exactly what the Maximum Subarray Sum problem is about! Using Kadane’s Algorithm, you can efficiently find the contiguous subarray with the largest sum in a one-dimensional array. This is a must-know for coding interviews and a great intro to dynamic programming. 🚀

In this guide, we’ll break down the problem, explain Kadane’s Algorithm step-by-step, and provide a clear solution for LeetCode 53. Let’s dive in! 😄

Problem Understanding

Given an array of integers (positive or negative), find the contiguous subarray (containing at least one number) with the largest sum and return that sum.

Example

• Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• Output: 6 (subarray: [4, -1, 2, 1])
• Explanation: The subarray [4, -1, 2, 1] has the largest sum of 6.

Constraints

• The array has at least one element.
• Elements can be positive, negative, or zero.
• 1 ≤ len(arr) ≤ 10^5

Pro Tip: Think of the problem as finding the “best streak” in a sequence of numbers. Kadane’s Algorithm makes this super efficient!

Approach: Kadane’s Algorithm

Kadane’s Algorithm is a dynamic programming technique that solves this problem in a single pass. It keeps track of the maximum sum ending at each position and the overall maximum sum found so far.

Algorithm

1. Initialize two variables:
   • max_current: The maximum sum of the subarray ending at the current index.
   • max_global: The maximum sum found across all subarrays.
   • Set both to the first element: max_current = max_global = arr[0].
2. Iterate through the array starting from the second element (i = 1 to len(arr) - 1):
   • Update max_current as the maximum of:
     • The current element alone: arr[i]
     • The current element plus the previous subarray sum: max_current + arr[i]
   • Update max_global if max_current is greater.
3. Return max_global as the maximum subarray sum.

Why It Works

At each step, Kadane’s Algorithm decides whether to start a new subarray at the current element or extend the existing subarray. This greedy choice ensures we capture the maximum sum efficiently.

Code Example

def kadane(arr):
    max_current = max_global = arr[0]
    
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        max_global = max(max_global, max_current)
    
    return max_global
 
# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane(arr))  # Output: 6

Complexity

• Time Complexity: O(n), where n is the length of the array (single pass).
• Space Complexity: O(1), as we only use two variables.

Why Use This?

• Pros: Simple, efficient, and optimal for finding the maximum subarray sum.
• Cons: Doesn’t return the subarray itself (can be modified to track indices if needed).

Visualizing Kadane’s Algorithm

Let’s walk through the example: [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Result: The maximum sum is 6, from the subarray [4, -1, 2, 1].

Edge Cases to Handle

1. Single Element: If the array has one element, return it (e.g., [-2] → -2).
2. All Negative Numbers: Kadane’s works correctly, returning the least negative number (e.g., [-2, -3, -1] → -1).
3. All Positive Numbers: Returns the sum of the entire array (e.g., [1, 2, 3] → 6).

Pro Tips for Interviews

1. Explain Intuition: Compare Kadane’s to choosing whether to “start fresh” or “continue” a streak at each step.
2. Handle Edge Cases: Mention single-element and all-negative cases to show thoroughness.
3. Modify for Subarray: If asked for the subarray itself, track start/end indices during the loop.
4. Visualize: Use a table (like above) or sketch the array to clarify your explanation.

Modified Code to Return Subarray

def kadane_with_subarray(arr):
    max_current = max_global = arr[0]
    start = end = temp_start = 0
    
    for i in range(1, len(arr)):
        if arr[i] > max_current + arr[i]:
            max_current = arr[i]
            temp_start = i
        else:
            max_current += arr[i]
        
        if max_current > max_global:
            max_global = max_current
            start = temp_start
            end = i
    
    return max_global, arr[start:end+1]
 
# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, subarray = kadane_with_subarray(arr)
print(max_sum, subarray)  # Output: 6, [4, -1, 2, 1]

Why Kadane’s Algorithm Shines

Kadane’s Algorithm is a perfect blend of simplicity and efficiency:

• Linear Time: O(n) makes it scalable for large arrays.
• Constant Space: O(1) ensures minimal memory usage.
• Versatile: Easily modified for variations (e.g., circular subarray, maximum product).

It’s a go-to solution for array-based problems and a staple in competitive programming.

Conclusion 🎯

You’re now equipped to solve the Maximum Subarray Sum problem (LeetCode 53) with confidence: ✅ Understand the problem and Kadane’s Algorithm ✅ Implement the solution with clear, efficient code ✅ Handle edge cases and explain your approach in interviews ✅ Extend the algorithm to return the subarray if needed

Kadane’s Algorithm is a powerful tool that’s both intuitive and efficient. Practice it, and you’ll be ready to tackle any subarray challenge! 🚀

Stay tuned for more algorithmic deep dives and coding tips! 🔥