Книга Теоретический минимум по Computer Science. Все что нужно программисту и разработчику, страница 51. Автор книги Владстон Феррейра Фило

Онлайн книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

Страница

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)

Дело в том, что нам незачем хранить день лучшей покупки для каждого дня на входе. Достаточно сохранить день лучшей покупки относительно дня лучшей продажи, найденной к настоящему моменту.

Страница