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-26 by Andrey BRATUS, Senior Data Analyst.
Kadane's algorithm Python code:
Kadane's algorithm Python code output:
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.
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)}" )
OUT: Maximum contiguous sum is 13