Maximum Subarray (Kadane's Algorithm) Algorithm Tutorial

Kadane's Algorithm

Kadane's Algorithm finds the maximum sum of any contiguous subarray in $O(n)$ time with a single pass. It's a classic example of dynamic programming with $O(1)$ space.

At each position, you decide whether to extend the previous subarray or start a new one. You extend if the previous sum is positive.

function maxSubarraySum(arr, n):
    maxSum = arr[0]
    currentSum = arr[0]

    for i from 1 to n - 1:
        currentSum = max(arr[i], currentSum + arr[i])
        maxSum = max(maxSum, currentSum)

    return maxSum

If your $currentSum$ becomes negative, starting fresh at the current element is always better than carrying the negative sum forward.

Tracking the subarray: To find the actual subarray indices, track start and end positions:

function maxSubarrayWithIndices(arr, n):
    maxSum = arr[0]
    currentSum = arr[0]
    start = 0
    end = 0
    tempStart = 0

    for i from 1 to n - 1:
        if arr[i] > currentSum + arr[i]:
            currentSum = arr[i]
            tempStart = i
        else:
            currentSum = currentSum + arr[i]
        if currentSum > maxSum:
            maxSum = currentSum
            start = tempStart
            end = i

    return (maxSum, start, end)

Applications: You use Kadane's algorithm for stock trading (max profit), signal processing, image processing, and finding optimal subarrays.

Time complexity: $O(n)$ with a single pass through the array.

Space complexity: $O(1)$ using only a few variables.