Kadane’s Algorithm: Maximum Subarray Sum

💡Strategies for Solving This Problem

Understanding Kadane's Algorithm

Kadane's algorithm finds the contiguous subarray with the largest sum in O(n) time. It's a classic dynamic programming problem and one of the most frequently asked interview questions.

Problem Statement

Given an array of integers, find the contiguous subarray with the maximum sum.

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6

Naive Approach: O(n²) or O(n³)

Check all possible subarrays - too slow for large inputs.

Kadane's Key Insight

At each position, decide: Should I extend the previous subarray or start fresh here?

If current_sum + nums[i] < nums[i], start new subarray at i.

Algorithm Steps

Initialize: max_sum = nums[0], current_sum = nums[0]
For each element from index 1:
- current_sum = max(nums[i], current_sum + nums[i])
- max_sum = max(max_sum, current_sum)
Return max_sum

Why It Works

Dynamic Programming:

dp[i] = maximum sum of subarray ending at index i
dp[i] = max(nums[i], dp[i-1] + nums[i])
Answer: max(dp)

Kadane's optimizes space from O(n) to O(1) by only tracking current and max.

Time Complexity

Time: O(n) - single pass through array
Space: O(1) - only two variables

Variations

Maximum Product Subarray: Track both max and min products
Maximum Circular Subarray: Consider wraparound
Maximum Sum Rectangle: 2D version using Kadane's
At Least K Elements: Kadane's with constraint

Common Interview Questions

Maximum Subarray (LeetCode 53): Classic Kadane's
Maximum Product Subarray (LeetCode 152): Modified for products
Maximum Sum Circular Subarray (LeetCode 918): Handle wraparound
Best Time to Buy and Sell Stock (LeetCode 121): Kadane's variant

Asked at: Amazon, Google, Facebook, Microsoft, Bloomberg

✅Solution

Solution: Kadane's Algorithm


def maxSubArray(nums):
    """
    LeetCode 53: Maximum Subarray

    Find contiguous subarray with largest sum

    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0

    max_sum = current_sum = nums[0]

    for i in range(1, len(nums)):
        # Either extend previous subarray or start fresh
        current_sum = max(nums[i], current_sum + nums[i])

        # Track global maximum
        max_sum = max(max_sum, current_sum)

    return max_sum

# Test
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 6
print(maxSubArray([1]))  # 1
print(maxSubArray([5,4,-1,7,8]))  # 23

Return Subarray Indices


def maxSubArrayWithIndices(nums):
    """
    Return (max_sum, start_index, end_index)
    """
    max_sum = current_sum = nums[0]
    start = end = 0
    temp_start = 0

    for i in range(1, len(nums)):
        # If starting fresh, update temp_start
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]

        # Update global max
        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    return (max_sum, start, end)

# Test
result = maxSubArrayWithIndices([-2,1,-3,4,-1,2,1,-5,4])
print(f"Sum: {result[0]}, Subarray: nums[{result[1]}:{result[2]+1}]")
# Sum: 6, Subarray: nums[3:7] = [4,-1,2,1]

Maximum Product Subarray


def maxProduct(nums):
    """
    LeetCode 152: Maximum Product Subarray

    Key difference: Track both max and min
    (negative * negative = positive)

    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0

    max_prod = min_prod = result = nums[0]

    for i in range(1, len(nums)):
        # If current number is negative, swap max and min
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod

        # Update max and min products
        max_prod = max(nums[i], max_prod * nums[i])
        min_prod = min(nums[i], min_prod * nums[i])

        # Update result
        result = max(result, max_prod)

    return result

# Test
print(maxProduct([2,3,-2,4]))  # 6 ([2,3])
print(maxProduct([-2,0,-1]))  # 0

Maximum Circular Subarray Sum


def maxSubarraySumCircular(nums):
    """
    LeetCode 918: Maximum Sum Circular Subarray

    Two cases:
    1. Max subarray doesn't wrap (normal Kadane's)
    2. Max subarray wraps around

    For case 2: Total sum - Min subarray = Max circular

    Time: O(n), Space: O(1)
    """
    def kadane_max(arr):
        max_sum = current_sum = arr[0]
        for num in arr[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum

    def kadane_min(arr):
        min_sum = current_sum = arr[0]
        for num in arr[1:]:
            current_sum = min(num, current_sum + num)
            min_sum = min(min_sum, current_sum)
        return min_sum

    total_sum = sum(nums)
    max_kadane = kadane_max(nums)
    min_kadane = kadane_min(nums)

    # If all numbers negative, return max (not circular)
    if max_kadane < 0:
        return max_kadane

    # Max of: normal subarray vs circular subarray
    max_circular = total_sum - min_kadane

    return max(max_kadane, max_circular)

# Test
print(maxSubarraySumCircular([1,-2,3,-2]))  # 3
print(maxSubarraySumCircular([5,-3,5]))  # 10 (circular: [5,5])

Best Time to Buy and Sell Stock


def maxProfit(prices):
    """
    LeetCode 121: Best Time to Buy and Sell Stock

    This is Kadane's in disguise!
    Track: max profit by selling today - min price seen so far

    Time: O(n), Space: O(1)
    """
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

# Can also solve using Kadane's on daily differences
def maxProfitKadane(prices):
    if len(prices) < 2:
        return 0

    max_profit = current_profit = 0

    for i in range(1, len(prices)):
        # Daily difference
        diff = prices[i] - prices[i-1]

        # Kadane's algorithm
        current_profit = max(0, current_profit + diff)
        max_profit = max(max_profit, current_profit)

    return max_profit

# Test
print(maxProfit([7,1,5,3,6,4]))  # 5 (buy at 1, sell at 6)
print(maxProfitKadane([7,1,5,3,6,4]))  # 5

Maximum Sum Rectangle in 2D Array


def maxSumRectangle(matrix):
    """
    Extend Kadane's to 2D

    Fix left and right columns, apply Kadane's on row sums

    Time: O(rows * cols^2), Space: O(rows)
    """
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')

    # Try all pairs of left and right columns
    for left in range(cols):
        temp = [0] * rows

        for right in range(left, cols):
            # Add current column to temp
            for i in range(rows):
                temp[i] += matrix[i][right]

            # Apply Kadane's on temp
            current_sum = temp[0]
            for i in range(1, rows):
                current_sum = max(temp[i], current_sum + temp[i])
                max_sum = max(max_sum, current_sum)

    return max_sum

Complexity Analysis

Standard Kadane's:

Time: O(n) - single pass
Space: O(1) - two variables

2D Version:

Time: O(rows * cols²)
Space: O(rows)

Key Insights

Kadane's is optimal for maximum subarray sum
Works by deciding at each step: extend or restart
Can be adapted for products, circular arrays, 2D
Classic dynamic programming with space optimization
If all numbers negative, return largest single number