the maximum subarray sum problem is the task of finding the maximum sum that can be obtained from a contiguous subarray within a given array of numbers for example given the array 2 1 3 4 1 2 1 5 4 the contiguous subarray with the maximum sum is 4 1 2 1 so the maximum subarray sum is 6 kadane s algorithm is a simple dynamic programming algorithm that solves the maximum subarray sum problem in on time and o1 space reference https en wikipedia orgwikimaximumsubarrayproblem solves the maximum subarray sum problem using kadane s algorithm param arr the given array of numbers param allowemptysubarrays if true then the algorithm considers empty subarrays maxsubarraysum2 8 9 19 maxsubarraysum0 0 0 maxsubarraysum1 0 0 0 1 0 1 0 maxsubarraysum1 2 3 4 2 10 maxsubarraysum2 1 3 4 1 2 1 5 4 6 maxsubarraysum2 3 9 8 2 8 maxsubarraysum2 3 1 4 6 1 maxsubarraysum2 3 1 4 6 allowemptysubarraystrue 0 maxsubarraysum 0 solves the maximum subarray sum problem using kadane s algorithm param arr the given array of numbers param allow_empty_subarrays if true then the algorithm considers empty subarrays max_subarray_sum 2 8 9 19 max_subarray_sum 0 0 0 max_subarray_sum 1 0 0 0 1 0 1 0 max_subarray_sum 1 2 3 4 2 10 max_subarray_sum 2 1 3 4 1 2 1 5 4 6 max_subarray_sum 2 3 9 8 2 8 max_subarray_sum 2 3 1 4 6 1 max_subarray_sum 2 3 1 4 6 allow_empty_subarrays true 0 max_subarray_sum 0
from collections.abc import Sequence


def max_subarray_sum(
    arr: Sequence[float], allow_empty_subarrays: bool = False
) -> float:
    
    if not arr:
        return 0

    max_sum = 0 if allow_empty_subarrays else float("-inf")
    curr_sum = 0.0
    for num in arr:
        curr_sum = max(0 if allow_empty_subarrays else num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)

    return max_sum


if __name__ == "__main__":
    from doctest import testmod

    testmod()

    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(f"{max_subarray_sum(nums) = }")