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
from collections.abc import Sequence


def max_subarray_sum(
    arr: Sequence[float], allow_empty_subarrays: bool = False
) -> float:
    """
    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
    """
    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) = }")
