Python/dynamic_programming/max_sub_array.py at master · FrogBattle/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
"""
author : Mayank Kumar Jha (mk9440)
"""
from __future__ importprint_function

importtime
importmatplotlib.pyplotasplt
fromrandomimportrandint
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)


if__name__=='__main__':
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()