Maximum sum of any subarray
December 16, 2023
Problem #
Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.
Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.
Do this in O(N) time.
Solution #
def max_subarray_sum(arr):
"""
Function to find the maximum sum of any contiguous subarray of an array.
This uses Kadane's Algorithm to solve the problem in O(N) time.
"""
max_sum = 0
current_sum = 0
for number in arr:
current_sum = max(0, current_sum + number)
max_sum = max(max_sum, current_sum)
return max_sum
# Test cases
test1 = [34, -50, 42, 14, -5, 86]
test2 = [-5, -1, -8, -9]
max_sum1 = max_subarray_sum(test1)
max_sum2 = max_subarray_sum(test2)
max_sum1, max_sum2