Arrays

Kadane's Algorithm

TimeO(n) SpaceO(1)

Imagine you’re walking along a trail collecting coins and hitting toll booths. At each step you decide: is it better to keep going (carry my running total forward) or start fresh from here? If your running total ever goes negative, starting over is always better.

When to use it: You need the maximum (or minimum) sum of a contiguous subarray. This is the classic “maximum subarray” problem.

Key insight: At each position, the maximum subarray ending here is either the current element alone or the current element plus the best subarray ending at the previous position. Take whichever is larger.

Common trap: Initializing maxSum to 0 instead of the first element. If all numbers are negative, you’d incorrectly return 0 instead of the least negative number.

function maxSubarraySum(arr):
    currentMax = arr[0]         # best subarray ending at current position
    globalMax = arr[0]          # best subarray found anywhere

    for i = 1 to length(arr) - 1:
        # Either extend the previous subarray or start fresh
        currentMax = max(arr[i], currentMax + arr[i])
        globalMax = max(globalMax, currentMax)

    return globalMax

def max_subarray_sum(arr: list[int]) -> int:
    current_max = arr[0]
    global_max = arr[0]

    for num in arr[1:]:
        current_max = max(num, current_max + num)
        global_max = max(global_max, current_max)

    return global_max


def max_subarray_with_indices(arr: list[int]) -> tuple[int, int, int]:
    """Returns (max_sum, start_index, end_index)."""
    current_max = arr[0]
    global_max = arr[0]
    start = end = temp_start = 0

    for i in range(1, len(arr)):
        if arr[i] > current_max + arr[i]:
            current_max = arr[i]
            temp_start = i
        else:
            current_max += arr[i]

        if current_max > global_max:
            global_max = current_max
            start = temp_start
            end = i

    return global_max, start, end

Problem: Given an integer array (which may contain negative numbers), find the contiguous subarray with the largest sum and return that sum.

How would you approach this?

Answer: This is Kadane's algorithm. At each index, decide whether to extend the current subarray or start a new one. The decision rule: if the running sum is negative, reset it. Track the global maximum across all positions.

Problem: You are given daily stock price changes (positive and negative). Find the maximum profit you could make from a single contiguous holding period.

How would you approach this?

Answer: This is Kadane's algorithm applied to the array of daily changes. The maximum subarray sum of the price-change array gives the best single buy-sell profit.

Time: O(n) because we make exactly one pass through the array, doing constant work per element (a comparison and an addition).

Space: O(1) because we only maintain two variables (currentMax and globalMax) regardless of input size.