Kadane's Algorithm

Kadane’s algorithm solves the maximum sum subarray problem, which involves finding a contiguous subarray with the largest sum within a one-dimensional array. It can be solved in $O(n)$ time and $O(1)$ space.

Formally, the problem is to find indices $i$ and $j$ with $1 \leq i \leq j \leq n$ such that

is maximized. For example, for the array of values $[−2, 1, −3, 4, −1, 2, 1, −5, 4]$, the contiguous subarray with the largest sum is $[4, −1, 2, 1]$, with sum $6$.

If we operate on the assumption that no empty subarrays are permitted, then the problem can be solved with the following code:

def max_subarray(numbers):
    best_sum = float('-inf')
    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 we allow for empty subarrays, we can make two changes to our code that allow us to default to an empty subarray:

• Initialize best_sum to 0
• Set current_sum in the loop to max(0, current_sum + x)

The runtime complexity is $O(n)$ and the space complexity is $O(1)$.