Maximum subarray problem

Kadane's algorithm scans the given array ${\displaystyle A[1\ldots n]}$ from left to right. In the ${\displaystyle j}$th step, it computes the subarray with the largest sum ending at ${\displaystyle j}$; this sum is maintained in variable current_sum.[note 3] Moreover, it computes the subarray with the largest sum anywhere in ${\displaystyle A[1\ldots j]}$, maintained in variable best_sum,[note 4] and easily obtained as the maximum of all values of current_sum seen so far, cf. line 7 of the algorithm.

As a loop invariant, in the ${\displaystyle j}$th step, the old value of current_sum holds the maximum over all ${\displaystyle i\in \{1,\ldots ,j-1\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j-1]}$. Therefore, current_sum${\displaystyle +A[j]}$[note 5] is the maximum over all ${\displaystyle i\in \{1,\ldots ,j-1\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j]}$. To extend the latter maximum to cover also the case ${\displaystyle i=j}$, it is sufficient to consider also the singleton subarray ${\displaystyle A[j\;\ldots \;j]}$. This is done in line 6 by assigning ${\displaystyle \max(A[j],}$current_sum${\displaystyle +A[j])}$ as the new value of current_sum, which after that holds the maximum over all ${\displaystyle i\in \{1,\ldots ,j\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j]}$.

Thus, the problem can be solved with the following code,[11] expressed in Python.

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = - infinity
    current_sum = 0
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

If the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is nonempty, its first element could be used in place of negative infinity, if needed to avoid mixing numeric and non-numeric values.

The algorithm can be adapted to the case which allows empty subarrays or to keep track of the starting and ending indices of the maximum subarray.

This algorithm calculates the maximum subarray ending at each position from the maximum subarray ending at the previous position, so it can be viewed as a trivial case of dynamic programming.

Example run
Execution of Kadane's algorithm on the above example array. Blue: subarray with largest sum ending at i; green: subarray with largest sum encountered so far; a lower case letter indicates an empty array; variable i is left implicit in Python code.

Kadane's original algorithm solves the problem variant when empty subarrays are admitted.[4][7] This variant will return 0 if the input contains no positive elements (including when the input is empty). It is obtained by two changes in code: in line 3, best_sum should be initialized to 0 to account for the empty subarray ${\displaystyle A[0\ldots -1]}$

    best_sum = 0;

and line 6 in the for loop current_sum should be updated as max(0, current_sum + x).[note 6]

        current_sum = max(0, current_sum + x)

As a loop invariant, in the ${\displaystyle j}$th step, the old value of current_sum holds the maximum over all ${\displaystyle i\in \{1,\ldots ,j\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j-1]}$.[note 7] Therefore, current_sum${\displaystyle +A[j]}$ is the maximum over all ${\displaystyle i\in \{1,\ldots ,j\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j]}$. To extend the latter maximum to cover also the case ${\displaystyle i=j+1}$, it is sufficient to consider also the empty subarray ${\displaystyle A[j+1\;\ldots \;j]}$. This is done in line 6 by assigning ${\displaystyle \max(0,}$current_sum${\displaystyle +A[j])}$ as the new value of current_sum, which after that holds the maximum over all ${\displaystyle i\in \{1,\ldots ,j+1\}}$ of the sum ${\displaystyle A[i]+\cdots +A[j]}$. Machine-verified C / Frama-C code of both variants can be found here.

The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well.

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of dynamic programming.

The runtime complexity of Kadane's algorithm is ${\displaystyle O(n)}$ and its space complexity is ${\displaystyle O(1)}$.[4][7]