Задача, которую давали на собеседованиях в Apple. От вас требуется написать функцию, которая возвращает максимальную прибыль от одной сделки с одной акцией (сначала покупка, потом продажа). Исходные данные — массив вчерашних котировок stock_prices_yesterday с ценами акций Apple.
Информация о массиве:
- Индекс равен количеству минут с начала торговой сессии (9:30 утра).
- Значение в массиве равно стоимости акции в это время.
Например: если акция в 10:00 утра стоила 20 долларов, то
stock_prices_yesterday[30] = 20.
Допустим, имеем некоторые условия:
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
profit = get_max_profit(stock_prices_yesterday)
#вернет 6 (купили за 5, продали за 11)
Массив может быть любым, хоть за весь день. Нужно написать функцию get_max_profit как можно эффективнее — с наименьшими затратами времени выполнения и памяти.
Решение
Для решения задачи недостаточно просто взять максимальную и минимальную цены, так как вы сначала должны купить по самой низкой цене, а затем продать по самой высокой, которая будет после цены покупки. Кроме того, если цена акции падает весь день, то лучшим ответом будет отрицательное число.
Для каждой цены будем проверять:
- возможность получить большую прибыль при покупке по min_price и продаже по current_price.
- обновилась ли min_price новым значением после итерации.
Инициализация:
- min_price равняется первой цене дня.
- max_profit равна первой прибыли, что мы получим.
Код решения (на Python):
def get_max_profit(stock_prices_yesterday):
# убедимся, что количество цен в массиве превышает 2
if len(stock_prices_yesterday) < 2:
raise IndexError('Получение прибыли требует как минимум двух цен в массиве')
# инициализируем min_price и max_profit
min_price = stock_prices_yesterday[0]
max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0]
for index, current_price in enumerate(stock_prices_yesterday):
# пропустим 0-ой элемент массива, так как min_price инициализирован.
# Также продавать в 0-й позиции нельзя
if index == 0:
continue
# вычисляем потенциальную прибыль
potential_profit = current_price - min_price
# обновляем максимальную прибыль
max_profit = max(max_profit, potential_profit)
# обновляем минимальную цену
min_price = min(min_price, current_price)
return max_profit
Эффективность полученного алгоритма — O(n) по времени и O(1) по памяти. Цикл проходит по массиву только один раз.
Источник: Interview Cake