Python/dynamic_programming/max_sub_array.py at master · imanghotbi-python/Python · GitHub

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
"""
author : Mayank Kumar Jha (mk9440)
"""
from __future__ importannotations


deffind_max_sub_array(a, low, high):
iflow==high:
returnlow, high, a[low]
else:
mid= (low+high) //2
left_low, left_high, left_sum=find_max_sub_array(a, low, mid)
right_low, right_high, right_sum=find_max_sub_array(a, mid+1, high)
cross_left, cross_right, cross_sum=find_max_cross_sum(a, 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
else:
returncross_left, cross_right, cross_sum


deffind_max_cross_sum(a, low, mid, high):
left_sum, max_left=-999999999, -1
right_sum, max_right=-999999999, -1
summ=0
foriinrange(mid, low-1, -1):
summ+=a[i]
ifsumm>left_sum:
left_sum=summ
max_left=i
summ=0
foriinrange(mid+1, high+1):
summ+=a[i]
ifsumm>right_sum:
right_sum=summ
max_right=i
returnmax_left, max_right, (left_sum+right_sum)


defmax_sub_array(nums: list[int]) ->int:
"""
 Finds the contiguous subarray which has the largest sum and return its sum.

 >>> max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])
 6

 An empty (sub)array has sum 0.
 >>> max_sub_array([])
 0

 If all elements are negative, the largest subarray would be the empty array,
 having the sum 0.
 >>> max_sub_array([-1, -2, -3])
 0
 >>> max_sub_array([5, -2, -3])
 5
 >>> max_sub_array([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
 187
 """
best=0
current=0
foriinnums:
current+=i
ifcurrent<0:
current=0
best=max(best, current)
returnbest


if__name__=="__main__":
"""
 A random simulation of this algorithm.
 """
importtime
fromrandomimportrandint

frommatplotlibimportpyplotasplt

inputs= [10, 100, 1000, 10000, 50000, 100000, 200000, 300000, 400000, 500000]
tim= []
foriininputs:
li= [randint(1, i) forjinrange(i)]
strt=time.time()
 (find_max_sub_array(li, 0, len(li) -1))
end=time.time()
tim.append(end-strt)
print("No of Inputs Time Taken")
foriinrange(len(inputs)):
print(inputs[i], "\t\t", tim[i])
plt.plot(inputs, tim)
plt.xlabel("Number of Inputs")
plt.ylabel("Time taken in seconds ")
plt.show()