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

COMING SOON!

```
"""
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.")
```