Kadane’s Algorithm in Python

Kadane’s Algorithm is used to find the subarray with the largest sum in a given array of integers. This algorithm operates in O(n) time complexity, making it very efficient for this problem.

Algorithm Explanation

The idea behind Kadane’s Algorithm is to iterate through the array while keeping track of the maximum sum of the subarray that ends at the current position. This is achieved using two variables:

• current_max: The maximum sum of the subarray that ends at the current position.
• global_max: The maximum sum of any subarray found so far.

For each element in the array, we update current_max as the maximum of the current element and the sum of the current element and the previous current_max. Then, we update global_max as the maximum of global_max and current_max.

Python Code Implementation

# Function to find the subarray with the largest sum
def find_max_subarray_sum(nums):
    # Initialize current_max and global_max with the first element of the array
    current_max = nums[0]
    global_max = nums[0]

    # Iterate through the array starting from the second element
    for num in nums[1:]:
        # Update current_max to the maximum of the current element and the sum of current element and current_max
        current_max = max(num, current_max + num)

        # Update global_max if current_max is greater than global_max
        if current_max > global_max:
            global_max = current_max

    # Return the global_max which is the largest sum of subarray found
    return global_max

# Main function to test the algorithm
if __name__ == "__main__":
    # Example array
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    # Find and print the maximum subarray sum
    max_subarray_sum = find_max_subarray_sum(nums)
    print("The maximum subarray sum is:", max_subarray_sum)

Explanation of the Python Code

In the Python code above:

• The function find_max_subarray_sum takes an array of integers as input and returns the sum of the subarray with the largest sum.
• We initialize current_max and global_max with the first element of the array.
• We iterate through the array starting from the second element. For each element, we update current_max and then global_max if necessary.
• The main function provides an example array and calls the find_max_subarray_sum function to find and print the maximum subarray sum.

Output

For the example array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the output will be:

The maximum subarray sum is: 6

The subarray with the largest sum is [4, -1, 2, 1] which sums to 6.