Kadane's algorithm.

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.

Kadane's algorithm.



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.



Kadane's algorithm Python code:



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





See also related topics: