kadanes Algorithm
This problem can be solved use several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is allowed). The maximal subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximal likelihood estimate of shapes in digitized pictures. There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximal subarray problem in O(n3−ε) time, for any ε>0, would imply a similarly fast algorithm for the all-pairs shortest paths problem. Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time,
better the brute force working time of O(n3).
"""
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.")
