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

Источник: Interview Cake

Задача, которую давали на собеседованиях в 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) по памяти. Цикл проходит по массиву только один раз.