Kadane’s Algorithm in Python

Kadane’s Algorithm is a popular algorithm used to find the maximum sum of a contiguous subarray in an array of integers. It operates in linear time, making it efficient for this problem.

1. Algorithm Explanation

Kadane’s Algorithm works by iterating through the array while maintaining two values:

• current_max: The maximum sum of the subarray that ends at the current position.
• global_max: The maximum sum encountered so far across all subarrays.

The algorithm updates these values as it processes each element of the array, ensuring that the result is the maximum possible sum of any contiguous subarray.

2. Python Implementation

Here’s a Python implementation of Kadane’s Algorithm:

def kadane_algorithm(arr):
    # Initialize variables
    current_max = global_max = arr[0]
    
    # Iterate through the array
    for num in arr[1:]:
        # Update current_max to be the maximum of current element or current_max plus element
        current_max = max(num, current_max + num)
        # Update global_max to be the maximum of global_max or current_max
        global_max = max(global_max, current_max)
    
    return global_max

# Example usage
arr = [1, -2, 3, 4, -1, 2, 1, -5, 4]
max_sum = kadane_algorithm(arr)
print(f"The maximum sum of a contiguous subarray is: {max_sum}")
    

3. Explanation of the Code

• Initialization: current_max and global_max are initialized to the first element of the array.
• Iteration: For each subsequent element, current_max is updated to be either the current element itself or the sum of the current element and the previous current_max.
• Global Maximum: global_max is updated if current_max exceeds it.

4. Example

Consider the array [1, -2, 3, 4, -1, 2, 1, -5, 4]. Kadane’s Algorithm finds that the maximum sum of a contiguous subarray is 9, corresponding to the subarray [3, 4, -1, 2, 1].

5. Conclusion

Kadane’s Algorithm is an efficient solution for finding the maximum sum of a contiguous subarray, with a time complexity of O(n). It is widely used in various applications, including financial analysis and signal processing, due to its simplicity and efficiency.