Repository navigation
Expand file tree
/
Copy pathmax_subarray.py
More file actions
113 lines (93 loc) · 3.41 KB
/
Copy pathmax_subarray.py
File metadata and controls
113 lines (93 loc) · 3.41 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
"""
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.
"""
from __future__ import annotations
import time
from collections.abc import Sequence
from random import randint
from matplotlib import pyplot as plt
def max_subarray(
arr: 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)
"""
if not arr:
return None, None, 0
if low == high:
return low, high, arr[low]
mid = (low + high) // 2
left_low, left_high, left_sum = max_subarray(arr, low, mid)
right_low, right_high, right_sum = max_subarray(arr, mid + 1, high)
cross_left, cross_right, cross_sum = max_cross_sum(arr, low, mid, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return left_low, left_high, left_sum
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_low, right_high, right_sum
return cross_left, cross_right, cross_sum
def max_cross_sum(
arr: Sequence[float], low: int, mid: int, high: int
) -> tuple[int, int, float]:
left_sum, max_left = float("-inf"), -1
right_sum, max_right = float("-inf"), -1
summ: int | float = 0
for i in range(mid, low - 1, -1):
summ += arr[i]
if summ > left_sum:
left_sum = summ
max_left = i
summ = 0
for i in range(mid + 1, high + 1):
summ += arr[i]
if summ > right_sum:
right_sum = summ
max_right = i
return max_left, max_right, (left_sum + right_sum)
def time_max_subarray(input_size: int) -> float:
arr = [randint(1, input_size) for _ in range(input_size)]
start = time.time()
max_subarray(arr, 0, input_size - 1)
end = time.time()
return end - start
def plot_runtimes() -> None:
input_sizes = [10, 100, 1000, 10000, 50000, 100000, 200000, 300000, 400000, 500000]
runtimes = [time_max_subarray(input_size) for input_size in input_sizes]
print("No of Inputs\t\tTime Taken")
for input_size, runtime in zip(input_sizes, runtimes):
print(input_size, "\t\t", runtime)
plt.plot(input_sizes, runtimes)
plt.xlabel("Number of Inputs")
plt.ylabel("Time taken in seconds")
plt.show()
if __name__ == "__main__":
"""
A random simulation of this algorithm.
"""
from doctest import testmod
testmod()