Kadane’s Algorithm: Maximum Subarray Sum Problem Solution with Examples

Kadane’s Algorithm is one of the most elegant and efficient algorithms in computer science. It is primarily used to solve the Maximum Subarray Sum Problem, which is a classic question in algorithm design. Given an array of positive and negative integers, the problem asks: What is the largest sum of any contiguous subarray?

This may sound simple, but the naive approach of checking all possible subarrays requires O(n²) or O(n³) time, which is inefficient for large arrays. Kadane’s Algorithm solves it in just O(n) time by using a clever dynamic programming approach.

Problem Statement

Given an array of integers (both positive and negative), find the maximum sum of a contiguous subarray. The subarray must contain at least one element.

Example

Input: [-2, -3, 4, -1, -2, 1, 5, -3]
Output: 7 (subarray [4, -1, -2, 1, 5])

How Kadane’s Algorithm Works

1. We iterate through the array while keeping track of:
   • max_ending_here: Maximum sum of subarray ending at the current element.
   • max_so_far: Global maximum sum found so far.
2. At each step, we check:

   max_ending_here = max(arr[i], max_ending_here + arr[i])
   max_so_far = max(max_so_far, max_ending_here)

3. This ensures we either start a new subarray at the current element or extend the previous subarray.

Kadane’s Algorithm in Python

def kadane_algorithm(arr):
    max_ending_here = arr[0]
    max_so_far = arr[0]
    
    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# Example usage
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
result = kadane_algorithm(arr)
print("Maximum Subarray Sum:", result)

Output:

Maximum Subarray Sum: 7

Step-by-Step Example Walkthrough

Let’s break down how the algorithm works for [-2, -3, 4, -1, -2, 1, 5, -3]:

Visualization of Algorithm Decision at Each Step

Complexity Analysis

• Time Complexity: O(n) (single pass over the array).
• Space Complexity: O(1) (only two variables are needed).

Advantages of Kadane’s Algorithm

• Efficient: Works in linear time.
• Simple and elegant.
• Can be extended to handle variations like 2D maximum sum subarray (Maximum Sub-rectangle problem).

Interactive Example

Try running this example interactively (e.g., in Jupyter Notebook or Code Sandbox):

arr = [1, -2, 3, 5, -3, 2]
print("Input Array:", arr)
print("Maximum Subarray Sum:", kadane_algorithm(arr))

Conclusion

Kadane’s Algorithm is a must-know dynamic programming approach for any programmer as it demonstrates how to reduce a seemingly complex problem into a simple linear traversal. Its application ranges from stock market profit analysis to resource allocation problems.