divide_and_conquer.max_subarray

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

max_cross_sum(→ tuple[int, int, float])
max_subarray(→ tuple[int | None, int | None, float])	Solves the maximum subarray problem using divide and conquer.
plot_runtimes(→ None)
time_max_subarray(→ float)

Module Contents

divide_and_conquer.max_subarray.max_cross_sum(arr: collections.abc.Sequence[float], low: int, mid: int, high: int) → tuple[int, int, float]

divide_and_conquer.max_subarray.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)

divide_and_conquer.max_subarray.plot_runtimes() → None

divide_and_conquer.max_subarray.time_max_subarray(input_size: int) → float