FilesExpand file tree

master

/

max_sub_array.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

94 lines (81 loc) · 2.57 KB

master

/

max_sub_array.py

Copy path

Top

File metadata and controls

• Code
• Blame

94 lines (81 loc) · 2.57 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

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 typing import List

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

for i in nums:

current += i

if current < 0:

current = 0

best = max(best, current)

return best

if __name__ == "__main__":

"""

A random simulation of this algorithm.

"""

import time

from random import randint

from matplotlib import pyplot as plt

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