dynamic_programming.max_subarray_sum
====================================

.. py:module:: dynamic_programming.max_subarray_sum

.. autoapi-nested-parse::

   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 O(n) time and O(1) space.

   Reference: https://en.wikipedia.org/wiki/Maximum_subarray_problem



Attributes
----------

.. autoapisummary::

   dynamic_programming.max_subarray_sum.nums


Functions
---------

.. autoapisummary::

   dynamic_programming.max_subarray_sum.max_subarray_sum


Module Contents
---------------

.. py:function:: max_subarray_sum(arr: collections.abc.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


.. py:data:: nums