Finding the maximum subarray sum in a list is a common algorithmic problem that can be efficiently solved using Kadane’s Algorithm. This algorithm operates in linear time, O(n), making it suitable for large datasets.
Python Function to Find Maximum Subarray Sum
Here is a Python function that implements Kadane's Algorithm to find the maximum sum of a contiguous subarray:
def maximum_subarray_sum(nums):
if not nums:
return 0
max_current = max_global = nums[0]
for num in nums[1:]:
max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current
return max_global
Explanation of the Code
- Initialization: The function starts by checking if the input list nums is empty. If it is, it returns 0, as there are no elements to consider. The variables max_current and max_global are initialized with the first element of the list, which serves as the starting point for the maximum calculations.
- Iterating Through the List: The function then iterates through the elements of the list starting from the second element. For each element num, it updates max_current, which keeps track of the maximum subarray sum that ends at the current position. The update is determined by comparing the current element itself against the sum of max_current and num. This step allows the algorithm to decide whether to start a new subarray or to continue the existing one.
- Updating Global Maximum: If the newly computed max_current exceeds max_global, it means a new overall maximum subarray sum has been found, and max_global is updated accordingly.
- Return Result: Finally, the function returns max_global, which contains the maximum sum of any contiguous subarray within nums.
Example Usage
Here is how to use the function:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = maximum_subarray_sum(nums)
print(f"The maximum subarray sum is: {result}") # Output: 6
In this example, the maximum subarray is [4, -1, 2, 1], which sums to 6.
Conclusion
Kadane's Algorithm is an efficient method for calculating the maximum subarray sum, making it a valuable tool in various computational problems involving arrays. The above implementation is straightforward and can be adapted or extended for more complex scenarios, such as handling multi-dimensional arrays or tracking the subarray indices.