Задача, которую давали на собеседованиях в Apple. От вас требуется написать функцию, которая возвращает максимальную прибыль от одной сделки с одной акцией (сначала покупка, потом продажа). Исходные данные — массив вчерашних котировок stock_prices_yesterday с ценами акций Apple.
Информация о массиве:
- Индекс равен количеству минут с начала торговой сессии (9:30 утра).
- Значение в массиве равно стоимости акции в это время.
Например: если акция в 10:00 утра стоила 20 долларов, то
stock_prices_yesterday[30] = 20.
Допустим, имеем некоторые условия:
1 2 3 4 | 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):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | 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