mirror of
https://github.com/TheAlgorithms/Python.git
synced 2024-10-05 21:29:29 +00:00
bc8df6de31
* [pre-commit.ci] pre-commit autoupdate updates: - [github.com/astral-sh/ruff-pre-commit: v0.2.2 → v0.3.2](https://github.com/astral-sh/ruff-pre-commit/compare/v0.2.2...v0.3.2) - [github.com/pre-commit/mirrors-mypy: v1.8.0 → v1.9.0](https://github.com/pre-commit/mirrors-mypy/compare/v1.8.0...v1.9.0) * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
62 lines
1.7 KiB
Python
62 lines
1.7 KiB
Python
"""
|
|
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
|
|
"""
|
|
|
|
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) = }")
|