|
| 1 | +""" |
| 2 | +author : Mayank Kumar Jha (mk9440) |
| 3 | +""" |
| 4 | + |
| 5 | +importtime |
| 6 | +importmatplotlib.pyplotasplt |
| 7 | +fromrandomimportrandint |
| 8 | +deffind_max_sub_array(A,low,high): |
| 9 | +iflow==high: |
| 10 | +returnlow,high,A[low] |
| 11 | +else : |
| 12 | +mid=(low+high)//2 |
| 13 | +left_low,left_high,left_sum=find_max_sub_array(A,low,mid) |
| 14 | +right_low,right_high,right_sum=find_max_sub_array(A,mid+1,high) |
| 15 | +cross_left,cross_right,cross_sum=find_max_cross_sum(A,low,mid,high) |
| 16 | +ifleft_sum>=right_sumandleft_sum>=cross_sum: |
| 17 | +returnleft_low,left_high,left_sum |
| 18 | +elifright_sum>=left_sumandright_sum>=cross_sum : |
| 19 | +returnright_low,right_high,right_sum |
| 20 | +else: |
| 21 | +returncross_left,cross_right,cross_sum |
| 22 | + |
| 23 | +deffind_max_cross_sum(A,low,mid,high): |
| 24 | +left_sum,max_left=-999999999,-1 |
| 25 | +right_sum,max_right=-999999999,-1 |
| 26 | +summ=0 |
| 27 | +foriinrange(mid,low-1,-1): |
| 28 | +summ+=A[i] |
| 29 | +ifsumm>left_sum: |
| 30 | +left_sum=summ |
| 31 | +max_left=i |
| 32 | +summ=0 |
| 33 | +foriinrange(mid+1,high+1): |
| 34 | +summ+=A[i] |
| 35 | +ifsumm>right_sum: |
| 36 | +right_sum=summ |
| 37 | +max_right=i |
| 38 | +returnmax_left,max_right,(left_sum+right_sum) |
| 39 | + |
| 40 | + |
| 41 | +if__name__=='__main__': |
| 42 | +inputs=[10,100,1000,10000,50000,100000,200000,300000,400000,500000] |
| 43 | +tim=[] |
| 44 | +foriininputs: |
| 45 | +li=[randint(1,i)forjinrange(i)] |
| 46 | +strt=time.time() |
| 47 | + (find_max_sub_array(li,0,len(li)-1)) |
| 48 | +end=time.time() |
| 49 | +tim.append(end-strt) |
| 50 | +print("No of Inputs Time Taken") |
| 51 | +foriinrange(len(inputs)): |
| 52 | +print(inputs[i],'\t\t',tim[i]) |
| 53 | +plt.plot(inputs,tim) |
| 54 | +plt.xlabel("Number of Inputs");plt.ylabel("Time taken in seconds ") |
| 55 | +plt.show() |
| 56 | + |
| 57 | + |
| 58 | + |
| 59 | + |
