Repository navigation
Expand file tree
/
Copy pathmax_subarray_sum.py
More file actions
61 lines (49 loc) · 1.73 KB
/
Copy pathmax_subarray_sum.py
File metadata and controls
61 lines (49 loc) · 1.73 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
"""
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) = }")