Python/divide_and_conquer/max_subarray.py at yash · Yashcodes04/Python · GitHub

Name: Python/divide_and_conquer/max_subarray.py at yash · Yashcodes04/Python · GitHub
Rating: 4.6 (9900 reviews)
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__ importannotations

importtime
fromcollections.abcimportSequence
fromrandomimportrandint

frommatplotlibimportpyplotasplt


defmax_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)
 """
ifnotarr:
returnNone, None, 0
iflow==high:
returnlow, 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)
ifleft_sum>=right_sumandleft_sum>=cross_sum:
returnleft_low, left_high, left_sum
elifright_sum>=left_sumandright_sum>=cross_sum:
returnright_low, right_high, right_sum
returncross_left, cross_right, cross_sum


defmax_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
foriinrange(mid, low-1, -1):
summ+=arr[i]
ifsumm>left_sum:
left_sum=summ
max_left=i

summ=0
foriinrange(mid+1, high+1):
summ+=arr[i]
ifsumm>right_sum:
right_sum=summ
max_right=i

returnmax_left, max_right, (left_sum+right_sum)


deftime_max_subarray(input_size: int) ->float:
arr= [randint(1, input_size) for_inrange(input_size)]
start=time.time()
max_subarray(arr, 0, input_size-1)
end=time.time()
returnend-start


defplot_runtimes() ->None:
input_sizes= [10, 100, 1000, 10000, 50000, 100000, 200000, 300000, 400000, 500000]
runtimes= [time_max_subarray(input_size) forinput_sizeininput_sizes]
print("No of Inputs\t\tTime Taken")
forinput_size, runtimeinzip(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.
 """
fromdoctestimporttestmod

testmod()