Arrays & StringsTemplate 4 of 9

Array & StringBasicO(n) time, O(1) space

Kadane's Algorithm

The Intuition

Kadane's algorithm solves the maximum-subarray problem in one pass and O(1) extra space. The reframing that makes it work: at every index i, the maximum subarray ending exactly at i is either just nums[i] alone, or nums[i] extended onto the maximum subarray ending at i-1. That gives a one-line recurrence:

current = max(nums[i], current + nums[i])
best = max(best, current)

The reason current resets when it goes negative: a negative running prefix can only hurt the next subarray, so dropping it never makes the answer worse. Equivalently, the recurrence picks nums[i] alone whenever current + nums[i] < nums[i], i.e., whenever the running prefix is negative.

The algorithm is a one-dimensional dynamic program in disguise. The DP state is "best subarray sum ending exactly at index i," and Kadane's collapses the DP table to a single variable because each state only depends on the previous one.

Two important variants come up in interviews:

Maximum product subarray. Track both the running max and the running min, because multiplying by a negative flips them. The new max is max(nums[i], max_so_far * nums[i], min_so_far * nums[i]).
Maximum circular subarray. The answer is either a normal Kadane's result, or the total sum minus the minimum subarray (the wrap-around case). Handle the all-negative input as a special case so you do not return zero.

When to use

Maximum subarray sum, maximum circular subarray, maximum product subarray (with modification), or any problem asking for an optimal contiguous segment.

When NOT to use

Non-contiguous subsets (use DP/backtracking)
Need the actual subarray indices alongside sum (need extra tracking)
2D subarray problems (use 2D prefix sum + Kadane)

Pattern Recognition

maximum subarray sumcontiguous subarray

Edge Cases

all negatives
single element
all zeros

Practice Problems

MediumMaximum Subarray

MediumMaximum Product Subarray

EasyBest Time to Buy and Sell Stock

MediumMaximum Sum Circular Subarray

Key Points

•Track current subarray sum and global maximum
•Reset current sum to 0 (or current element) when it goes negative
•Works in a single pass. No need for prefix sums.
•Can be extended to track the subarray boundaries (start/end indices)
•Handles all-negative arrays by initializing max to first element

Code Template

def max_subarray(nums):
    """Maximum subarray sum (Kadane's algorithm)."""
    max_sum = curr_sum = nums[0]
    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)
    return max_sum

def max_subarray_with_indices(nums):
    """Return (max_sum, start, end) of the maximum subarray."""
    max_sum = curr_sum = nums[0]
    start = end = temp_start = 0

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

        if curr_sum > max_sum:
            max_sum = curr_sum
            start, end = temp_start, i

    return max_sum, start, end

def max_circular_subarray(nums):
    """Maximum subarray sum in a circular array."""
    total = sum(nums)
    max_kadane = max_subarray(nums)

    # Min subarray to find max circular = total - min_subarray
    min_sum = curr_min = nums[0]
    for num in nums[1:]:
        curr_min = min(num, curr_min + num)
        min_sum = min(min_sum, curr_min)

    # If all elements are negative, max_kadane is the answer
    if min_sum == total:
        return max_kadane
    return max(max_kadane, total - min_sum)

func maxSubarray(nums []int) int {
    // Maximum subarray sum (Kadane's algorithm).
    maxSum, currSum := nums[0], nums[0]
    for _, num := range nums[1:] {
        if num > currSum+num {
            currSum = num
        } else {
            currSum += num
        }
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return maxSum
}

func maxCircularSubarray(nums []int) int {
    // Maximum subarray sum in a circular array.
    total := 0
    for _, n := range nums {
        total += n
    }
    maxKadane := maxSubarray(nums)

    // Find min subarray
    minSum, currMin := nums[0], nums[0]
    for _, num := range nums[1:] {
        if num < currMin+num {
            currMin = num
        } else {
            currMin += num
        }
        if currMin < minSum {
            minSum = currMin
        }
    }

    if minSum == total {
        return maxKadane
    }
    if total-minSum > maxKadane {
        return total - minSum
    }
    return maxKadane
}

public int maxSubarray(int[] nums) {
    // Maximum subarray sum (Kadane's algorithm).
    int maxSum = nums[0], currSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
}

public int maxCircularSubarray(int[] nums) {
    // Maximum subarray sum in a circular array.
    int total = 0;
    for (int n : nums) total += n;
    int maxKadane = maxSubarray(nums);

    int minSum = nums[0], currMin = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currMin = Math.min(nums[i], currMin + nums[i]);
        minSum = Math.min(minSum, currMin);
    }

    if (minSum == total) return maxKadane;
    return Math.max(maxKadane, total - minSum);
}

Common Mistakes

Initializing max_sum to 0 instead of arr[0] (fails on all-negative arrays)
Forgetting to handle the empty array edge case
Not resetting current_sum correctly. Should compare element vs current_sum + element

Related Patterns

CrackingWalnuts