# Mastering Kadane's Algorithm in Python for Optimal Results.

## MAX SUM subarray use case.

In computer science the Kadane's algorithm or the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array (list) of numbers. As a initial condition each number in the input array A could be positive, negative, or zero.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.

If the array contains only positive numbers then the problem is easy, a maximum subarray is the entire array. 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. Several different sub-arrays can have the same maximum sum. Typical use cases of Kadane's algorithm are computer vision tasks and genomic sequence analysis.

1. ## Kadane's algorithm Python code:

2. ``````
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
A = [2, 3, 4, 1, 2, 1, -5, -3]
print(f"Maximum contiguous sum is {max_subarray(A)}" )
``````
3. ## Kadane's algorithm Python code output:

4. OUT: Maximum contiguous sum is 13