Задача про акции Apple

Задача, которую давали на собеседованиях в Apple. От вас требуется написать функцию, которая возвращает максимальную прибыль от одной сделки с одной акцией (сначала покупка, потом продажа). Исходные данные — массив вчерашних котировок stock_prices_yesterday с ценами акций Apple. 

Информация о массиве:

  • Индекс равен количеству минут с начала торговой сессии (9:30 утра).
  • Значение в массиве равно стоимости акции в это время.

Например: если акция в 10:00 утра стоила 20 долларов, то
stock_prices_yesterday[30] = 20.

Допустим, имеем некоторые условия:

Массив может быть любым, хоть за весь день. Нужно написать функцию get_max_profit как можно эффективнее — с наименьшими затратами времени выполнения и памяти.

Решение

Для решения задачи недостаточно просто взять максимальную и минимальную цены, так как вы сначала должны купить по самой низкой цене, а затем продать по самой высокой, которая будет после цены покупки. Кроме того, если цена акции падает весь день, то лучшим ответом будет отрицательное число.

Для каждой цены будем проверять:

  • возможность получить большую прибыль при покупке по min_price и продаже по current_price.
  • обновилась ли min_price новым значением после итерации.

Инициализация:

  • min_price равняется первой цене дня.
  • max_profit равна первой прибыли, что мы получим.

Код решения (на Python):

Эффективность полученного алгоритма — O(n) по времени и O(1) по памяти. Цикл проходит по массиву только один раз.

Источник: Interview Cake