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.

Kadane's algorithm.
Kadane's algorithm meme.

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





See also related topics: