FilesExpand file tree

 Write-for-current-Python

/

kadanes.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (55 loc) · 1.92 KB

 Write-for-current-Python

/

kadanes.py

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (55 loc) · 1.92 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

"""

Kadane's algorithm to get maximum subarray sum

https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d

https://en.wikipedia.org/wiki/Maximum_subarray_problem

"""

test_data: tuple = ([-2, -8, -9], [2, 8, 9], [-1, 0, 1], [0, 0], [])

def negative_exist(arr: list) -> int:

"""

>>> negative_exist([-2,-8,-9])

-2

>>> [negative_exist(arr) for arr in test_data]

[-2, 0, 0, 0, 0]

"""

arr = arr or [0]

max = arr[0]

for i in arr:

if i >= 0:

return 0

elif max <= i:

max = i

return max

def kadanes(arr: list) -> int:

"""

If negative_exist() returns 0 than this function will execute

else it will return the value return by negative_exist function

For example: arr = [2, 3, -9, 8, -2]

Initially we set value of max_sum to 0 and max_till_element to 0 than when

max_sum is less than max_till particular element it will assign that value to

max_sum and when value of max_till_sum is less than 0 it will assign 0 to i

and after that whole process, return the max_sum

So the output for above arr is 8

>>> kadanes([2, 3, -9, 8, -2])

8

>>> [kadanes(arr) for arr in test_data]

[-2, 19, 1, 0, 0]

"""

max_sum = negative_exist(arr)

if max_sum < 0:

return max_sum

max_sum = 0

max_till_element = 0

for i in arr:

max_till_element += i

if max_sum <= max_till_element:

max_sum = max_till_element

if max_till_element < 0:

max_till_element = 0

return max_sum

if __name__ == "__main__":

try:

print("Enter integer values sepatated by spaces")

arr = [int(x) for x in input().split()]

print(f"Maximum subarray sum of {arr} is {kadanes(arr)}")

except ValueError:

print("Please enter integer values.")