function trade_kadane(prices):
····sell_day ← 1
····buy_day ← 1
····best_profit ← 0
····for each s from 2 to prices.length
········if prices[s] < prices[buy_day]
············b ← s
········else
············b ← buy_day
········profit ← prices[s] — prices[b]
········if profit > best_profit
············sell_day ← s
············buy_day ← b
············best_profit ← profit
····return (sell_day, buy_day)
Дело в том, что нам незачем хранить день лучшей покупки для каждого дня на входе. Достаточно сохранить день лучшей покупки относительно дня лучшей продажи, найденной к настоящему моменту.