Implement a Function to Find Maximum Sum of Subarray in Python

In Python, you can implement a function that efficiently finds the maximum sum of a subarray with a time complexity of O(n) by following this code:

def max_subarray_sum(arr):
    max_sum = arr[0]
    current_sum = arr[0]
    
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# Example usage
input_list = [1, -2, 3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(input_list)
print("Maximum sum of a subarray:", result)

This code snippet defines a function max_subarray_sum that takes a list of integers as input and returns the maximum sum of a subarray where the subarray must consist of consecutive elements from the original list. The function achieves O(n) time complexity by iterating through the list once and calculating the maximum sum dynamically.