Python/dynamic_programming/max_sub_array.py at master · wcfylcf/Python · GitHub

History

60 lines (52 loc) · 1.74 KB

Raw

"""

author : Mayank Kumar Jha (mk9440)

"""

from __future__ import print_function

import time

import matplotlib.pyplot as plt

from random import randint

def find_max_sub_array(A,low,high):

if low==high:

return low,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)

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

else:

return cross_left,cross_right,cross_sum

def find_max_cross_sum(A,low,mid,high):

left_sum,max_left=-999999999,-1

right_sum,max_right=-999999999,-1

summ=0

for i in range(mid,low-1,-1):

summ+=A[i]

if summ > left_sum:

left_sum=summ

max_left=i

summ=0

for i in range(mid+1,high+1):

summ+=A[i]

if summ > right_sum:

right_sum=summ

max_right=i

return max_left,max_right,(left_sum+right_sum)

if __name__=='__main__':

inputs=[10,100,1000,10000,50000,100000,200000,300000,400000,500000]

tim=[]

for i in inputs:

li=[randint(1,i) for j in range(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")

for i in range(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()

Python/dynamic_programming/max_sub_array.py at master · wcfylcf/Python · GitHub

Expand file tree

Breadcrumbs

max_sub_array.py

Latest commit

History

Breadcrumbs

max_sub_array.py

File metadata and controls