Kadane's Algorithm

    DSA · Intermediate

    Definition

    Kadane's algorithm finds the maximum-sum contiguous subarray by extending or restarting a running sum.

    A classic O(n) dynamic-programming interview problem.

    Diagram

    -2 1 -3 4 -1 2 1best window 4 -1 2 1sum 6

    Flowchart

    cur = best = a[0]For each x: cur = max(x, cur + x)best = max(best, cur)Return best

    Example: Maximum subarray

    a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
cur = best = a[0]
for x in a[1:]:
    cur = max(x, cur + x)
    best = max(best, cur)
print(best)

    Output: 6

    Complexity

    O(n) time · O(1) space

    Key points

    • Restart when running sum hurts
    • Works with all-negative arrays

    Interview questions

    How to also return indexes?

    Track the start when you restart and record start/end when best updates.

    More DSA topics

    ArraysLinked ListStackQueue