FilesExpand file tree

 master

/

max_sub_array.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

79 lines (71 loc) · 2.14 KB

 master

/

max_sub_array.py

Copy path

Top

File metadata and controls

• Code
• Blame

79 lines (71 loc) · 2.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

author : Mayank Kumar Jha (mk9440)

"""

from typing import List

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)

def max_sub_array(nums: List[int]) -> int:

"""

Finds the contiguous subarray (can be empty array)

which has the largest sum and return its sum.

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

6

>>> max_sub_array([])

0

>>> max_sub_array([-1,-2,-3])

0

"""

best = 0

current = 0

for i in nums:

current += i

if current < 0:

current = 0

best = max(best, current)

return best

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()