Home Blog Links Now

Kadane's Algorithm

2021-12-12 python algorithms

Possible usecase: Maximum subarray problem.

Steps

  1. Initialize two variables: max_sum = current_sum = 0
  2. Loop through numbers in list
    • Set current_sum = max(0, current_sum + list[i])
    • Set max_sum = max(max_sum, current_sum)
  3. Return max_sum

Caveats 1, 2

Solving Best Time to Buy and Sell Stock with Kadane's Algorithm

Slightly tweak the algorithm to track max profit and min price.

def maxProfit(self, prices: List[int]) -> int:
    max_profit, min_price = 0, float("inf")
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

  1. Wikipedia: Maximum subarray problem ↩︎

  2. SO: Kadane Algorithm Negative Numbers ↩︎