dynamic_programming.max_subarray_sum

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

nums

Functions

max_subarray_sum(→ float)

Solves the maximum subarray sum problem using Kadane's algorithm.

Module Contents

dynamic_programming.max_subarray_sum.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

dynamic_programming.max_subarray_sum.nums