Find the Maximum Subarray Sum Using Kadane’s Algorithm

Finding the maximum sum of a contiguous subarray within a larger array is a classic problem in computer science. While brute-force approaches exist, they’re inefficient for larger arrays. Kadane’s Algorithm provides an elegant and efficient solution with a time complexity of O(n), making it ideal for practical applications. This blog post will look at Kadane’s Algorithm and demonstrate its implementation in Python.

Understanding the Problem

Given an array of integers (positive, negative, or zero), the goal is to find the subarray (contiguous sequence of elements) that has the largest sum. For example:

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The maximum contiguous subarray sum is 6, achieved by the subarray [4, -1, 2, 1].

Kadane’s Algorithm Explained

Kadane’s Algorithm works iteratively, keeping track of the maximum sum encountered so far and the current maximum sum. Here’s the core idea:

1. Initialization: Start with max_so_far and max_ending_here both set to the first element of the array.

2. Iteration: Iterate through the array, starting from the second element. For each element:

   • Update max_ending_here by adding the current element to it. If max_ending_here becomes negative, reset it to 0.

   • If max_ending_here is greater than max_so_far, update max_so_far.

3. Result: After iterating through the entire array, max_so_far will hold the maximum subarray sum.

Python Implementation

Here’s a Python function implementing Kadane’s Algorithm:

def kadanes_algorithm(arr):
    """
    Finds the maximum subarray sum using Kadane's Algorithm.

    Args:
        arr: A list of integers.

    Returns:
        The maximum subarray sum.  Returns 0 for an empty array.
    """
    if not arr:
        return 0

    max_so_far = arr[0]
    max_ending_here = 0

    for i in range(len(arr)):
        max_ending_here += arr[i]
        if max_ending_here < 0:
            max_ending_here = 0
        elif max_so_far < max_ending_here:
            max_so_far = max_ending_here

    return max_so_far

#Example Usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = kadanes_algorithm(arr)
print(f"The maximum subarray sum is: {max_sum}") # Output: 6

arr2 = [-1,-2,-3]
max_sum2 = kadanes_algorithm(arr2)
print(f"The maximum subarray sum is: {max_sum2}") # Output: -1

arr3 = []
max_sum3 = kadanes_algorithm(arr3)
print(f"The maximum subarray sum is: {max_sum3}") # Output: 0

This code effectively demonstrates the algorithm, handling both positive and negative integer arrays including empty ones. The comments improve readability and understanding. You can easily modify this code to your specific needs. This efficient algorithm is a tool for solving various optimization problems involving subarrays.