divide_and_conquer.max_subarray
===============================

.. py:module:: divide_and_conquer.max_subarray

.. autoapi-nested-parse::

   The maximum subarray problem is the task of finding the continuous subarray that has the
   maximum sum 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], which has a sum of 6.

   This divide-and-conquer algorithm finds the maximum subarray in O(n log n) time.



Functions
---------

.. autoapisummary::

   divide_and_conquer.max_subarray.max_cross_sum
   divide_and_conquer.max_subarray.max_subarray
   divide_and_conquer.max_subarray.plot_runtimes
   divide_and_conquer.max_subarray.time_max_subarray


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

.. py:function:: max_cross_sum(arr: collections.abc.Sequence[float], low: int, mid: int, high: int) -> tuple[int, int, float]

.. py:function:: max_subarray(arr: collections.abc.Sequence[float], low: int, high: int) -> tuple[int | None, int | None, float]

   Solves the maximum subarray problem using divide and conquer.
   :param arr:     the given array of numbers
   :param low:     the start index
   :param high:    the end index
   :return:        the start index of the maximum subarray, the end index of the
                   maximum subarray, and the maximum subarray sum

   >>> nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
   >>> max_subarray(nums, 0, len(nums) - 1)
   (3, 6, 6)
   >>> nums = [2, 8, 9]
   >>> max_subarray(nums, 0, len(nums) - 1)
   (0, 2, 19)
   >>> nums = [0, 0]
   >>> max_subarray(nums, 0, len(nums) - 1)
   (0, 0, 0)
   >>> nums = [-1.0, 0.0, 1.0]
   >>> max_subarray(nums, 0, len(nums) - 1)
   (2, 2, 1.0)
   >>> nums = [-2, -3, -1, -4, -6]
   >>> max_subarray(nums, 0, len(nums) - 1)
   (2, 2, -1)
   >>> max_subarray([], 0, 0)
   (None, None, 0)


.. py:function:: plot_runtimes() -> None

.. py:function:: time_max_subarray(input_size: int) -> float