Python – Apply Kadane’s Algorithm for the Maximum Sum Subarray

Kadane’s Algorithm is a popular method used to solve the Maximum Sum Subarray problem efficiently. In this tutorial, we will learn how to implement Kadane’s Algorithm in Python. This algorithm finds the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

Problem Statement

Given an array arr of integers (which may include negative numbers), determine the contiguous subarray with the largest sum and return that sum.

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
# Explanation: The maximum sum subarray is [4, -1, 2, 1] which sums to 6.

Example 2:

</>
Copy
Input: arr = [1, 2, 3, 4]
Output: 10
# Explanation: The entire array forms the maximum sum subarray.

Solution Approach

Kadane’s Algorithm works by iterating through the array while keeping track of the maximum subarray sum ending at the current index. The steps are as follows:

  1. Initialize: Set two variables max_current and max_global to the first element of the array.
  2. Iterate: Loop through the array starting from the second element. For each element x:
    • Update max_current as the maximum of x and max_current + x.
    • If max_current is greater than max_global, update max_global with the value of max_current.
  3. Result: After the loop ends, max_global will hold the maximum sum of any contiguous subarray.

This algorithm runs in O(n) time, making it very efficient for large arrays.

Python Program

</>
Copy
def kadane_max_subarray(arr):
    """
    Function to find the maximum sum of a contiguous subarray using Kadane's Algorithm.
    
    Parameters:
        arr (list): List of integers (can include negative numbers)
        
    Returns:
        int: Maximum subarray sum
    """
    # Initialize max_current and max_global with the first element
    max_current = max_global = arr[0]
    
    # Loop through the array starting from the second element
    for num in arr[1:]:
        # Calculate the maximum sum ending at the current position
        max_current = max(num, max_current + num)
        
        # Update max_global if needed
        if max_current > max_global:
            max_global = max_current
            
    return max_global

# Example usage:

# Example 1
arr1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Sum (Example 1):", kadane_max_subarray(arr1))  # Expected Output: 6

# Example 2
arr2 = [1, 2, 3, 4]
print("Maximum Sum (Example 2):", kadane_max_subarray(arr2))  # Expected Output: 10

The above program defines a function kadane_max_subarray that implements Kadane’s Algorithm. It then demonstrates the function using two examples with different input arrays.

Conclusion

Kadane’s Algorithm is an elegant and efficient solution for the Maximum Sum Subarray problem. Its linear time complexity makes it suitable for large datasets.