FilesExpand file tree

 all-permutations

/

max_subarray_sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (51 loc) · 2 KB

 all-permutations

/

max_subarray_sum.py

Top

File metadata and controls

• Code
• Blame

75 lines (51 loc) · 2 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

"""

Given a array of length n, max_subarray_sum() finds

the maximum of sum of contiguous sub-array using divide and conquer method.

Time complexity : O(n log n)

Ref : INTRODUCTION TO ALGORITHMS THIRD EDITION

(section : 4, sub-section : 4.1, page : 70)

"""

def max_sum_from_start(array):

""" This function finds the maximum contiguous sum of array from 0 index

Parameters :

array (list[int]) : given array

Returns :

max_sum (int) : maximum contiguous sum of array from 0 index

"""

array_sum = 0

max_sum = float("-inf")

for num in array:

array_sum += num

if array_sum > max_sum:

max_sum = array_sum

return max_sum

def max_cross_array_sum(array, left, mid, right):

""" This function finds the maximum contiguous sum of left and right arrays

Parameters :

array, left, mid, right (list[int], int, int, int)

Returns :

(int) : maximum of sum of contiguous sum of left and right arrays

"""

max_sum_of_left = max_sum_from_start(array[left:mid+1][::-1])

max_sum_of_right = max_sum_from_start(array[mid+1: right+1])

return max_sum_of_left + max_sum_of_right

def max_subarray_sum(array, left, right):

""" Maximum contiguous sub-array sum, using divide and conquer method

Parameters :

array, left, right (list[int], int, int) :

given array, current left index and current right index

Returns :

int : maximum of sum of contiguous sub-array

"""

# base case: array has only one element

if left == right:

return array[right]

# Recursion

mid = (left + right) // 2

left_half_sum = max_subarray_sum(array, left, mid)

right_half_sum = max_subarray_sum(array, mid + 1, right)

cross_sum = max_cross_array_sum(array, left, mid, right)

return max(left_half_sum, right_half_sum, cross_sum)

array = [-2, -5, 6, -2, -3, 1, 5, -6]

array_length = len(array)

print("Maximum sum of contiguous subarray:", max_subarray_sum(array, 0, array_length - 1))