Вот типичная задачка на собеседованиях в ИТ-компании. Если вы решите её, будете королём собеседований (или королевой):
Есть список цен, сколько стоил некий товар в разные дни. Например, это ценная бумага. Нужно написать код, который скажет, в какой день нужно было покупать, а в какой — продавать этот товар, чтобы получить максимальную прибыль. Сначала товар нужно купить, потом продать. Если цены идут так, что прибыли не получается, — тоже сообщить об этом.
Примеры списка и ответов:
prices = [7,1,5,3,6,4] ← максимальная прибыль 5, если купить по цене 1 во второй день, а продать за 6 на пятый день;
prices = [7,6,4,3,1] ← прибыли нет (потому что цена всё время снижается).
Логика решения
Разобьём алгоритм на такие этапы:
- Гигиена и безопасность. Проверяем, есть ли вообще цены в списке. Если нет — выводим сообщение.
- Если цены есть, находим максимальную прибыль, которую можно получить. Для этого находим разницу между минимальным и максимальным значением, которые идут именно в таком порядке, слева направо.
- Если прибыль в итоге равна нулю — тоже выводим сообщение, что нет смысла ничего покупать.
- Если прибыль больше нуля — выводим дни, когда нужно покупать и продавать.
Первые три пункта простые, а в четвёртом есть подвох.
Проверяем, есть ли цены в списке
Начнём решение с очевидного: если цен в списке нет, то выводим сообщение про это и останавливаем скрипт:
# список цены на товар в разные дни
prices = [7,1,5,1,9,4]
# если список цен пустой — выводим сообщение
if len(prices) == 0:
print('Цен нет')
# останавливаем скрипт
exit()Если мы поменяем список цен на пустой (prices = []) и запустим скрипт, то получим сообщение, что там нет цен:
Если цены есть — находим прибыль
Теперь, раз цены есть, посчитаем прибыль. Для этого нам понадобятся три переменные:
- profit — тут будет наша максимальная прибыль, которую можно получить;
- minIndex — номер элемента с наименьшей ценой;
- minBuy — минимальная цена, по которой нужно купить товар для максимальной прибыли.
Сделаем простой цикл, где на каждом шаге мы будем брать очередную пару цен и смотреть — будет ли с ними прибыль больше, чем раньше. Если будет — запоминаем прибыль и номер элемента с минимальной ценой. Добавим новый код к предыдущему условию:
# список цены на товар в разные дни
prices = [7,1,5,1,9,4]
# если список цен пустой - выводим сообщение
if len(prices) == 0:
print('Цен нет')
# останавливаем скрипт
exit()
# если цены есть
else:
# прибыль на старте нулевая
profit = 0
# номер элемента с наименьшей ценой
minIndex = 0
# первая цена пусть будет на старте минимальной
minBuy = prices[0]
# перебираем все цены
for i in range(len(prices)):
# находим прибыль на текущем шаге
# если она больше предыдущей — берём новую прибыль
if profit < prices[i] - minBuy:
profit = prices[i] - minBuy
# запоминаем позицию минимальной цены
minIndex = prices.index(min(minBuy, prices[i]))
# устанавливаем минимальное значение, если текущее меньше минимального
minBuy = min(minBuy, prices[i])Сообщаем о нулевой прибыли
Здесь всё просто: если прибыль равна нулю, то выводим сообщение и тоже останавливаем программу:
# если прибыль нулевая
if profit == 0:
# выводим сообщение и останавливаем программу
print('Нет оптимальных дней для покупки')
exit()
Выводим оптимальные дни для покупки и продажи
А вот на этом этапе на собеседованиях часто допускают ошибку: раз мы знаем прибыль и минимальную стоимость, то легко узнать максимальную стоимость, сложив эти два числа. И раз мы знаем теперь эту стоимость, то можно найти индекс в списке по значению элемента.
Ошибка здесь в том, что это работает только для случаев, когда в списке максимальная нужная стоимость стоит после минимальной. Но если она встречается два раза — до и после минимальной, — то такая логика даёт сбой.
Допустим, у нас список цен выглядит так:
prices = [7,1,5,1,7,4]
Семёрка здесь встречается два раза — в начале и в середине. Если мы будем использовать такую логику, то команда [prices.index[profit+prices[minIndex]] вернёт только первый найденный элемент, а это будет неправильно.
Чтобы избежать этой ошибки, нам нужно проверять, стоит ли индекс максимальной стоимости после минимальной. Если стоит — его можно заменить на ноль, чтобы он не мешал при дальнейших расчётах. Для этого сделаем копию списка цен и будем менять значения в нём, чтобы не трогать исходные цены:
# копируем список цен
prices_copy = prices
# перебираем все цены
for i in range(len(prices)):
# находим первый индекс максимальной цены
sell = prices_copy.index(profit+prices[minIndex])
# если максимальная цена стоит раньше минимальной
if sell < minIndex:
# меняем её на нулевую, чтобы не учитывать её на следующих шагах, и переходим к следующему шагу цикла
prices_copy[sell] = 0
pass
# если максимальная цена стоит после минимальной — останавливаем цикл, мы нашли то, что хотели
else:
break
# выводим результаты
print('Покупка: на ' + str(minIndex+1) + ' день по цене ' + str(prices[minBuy]))
print('Продажа: на ' + str(sell+1) + ' день по цене ' + str(prices_copy[sell]))
print('Прибыль — ' +str(profit))При выводе мы прибавляем единицу для того, чтобы компенсировать отчёт элементов списка с нуля — компьютер считает так, а мы считаем с единицы.
Запустим скрипт с исходными данными (7,1,5,1,9,4) и посмотрим, что получилось:
# список цены на товар в разные дни
prices = [7,1,5,1,9,4]
# если список цен пустой - выводим сообщение
if len(prices) == 0:
print('Цен нет')
# останавливаем скрипт
exit()
# если цены есть
else:
# прибыль на старте нулевая
profit = 0
# номер элемента с наименьшей ценой
minIndex = 0
# первая цена пусть будет на старте минимальной
minBuy = prices[0]
# перебираем все цены
for i in range(len(prices)):
# находим прибыль на текущем шаге
# если она больше предыдущей — берём новую прибыль
if profit < prices[i] - minBuy:
profit = prices[i] - minBuy
# запоминаем позицию минимальной цены
minIndex = prices.index(min(minBuy, prices[i]))
# устанавливаем минимальное значение, если текущее меньше минимального
minBuy = min(minBuy, prices[i])
# если прибыль нулевая
if profit == 0:
# выводим сообщение и останавливаем программу
print('Нет оптимальных дней для покупки')
exit()
# копируем список цен
prices_copy = prices
# перебираем все цены
for i in range(len(prices)):
# находим первый индекс максимальной цены
sell = prices_copy.index(profit+prices[minIndex])
# если максимальная цена стоит раньше минимальной
if sell < minIndex:
# меняем её на нулевую, чтобы не учитывать её на следующих шагах, и переходим к следующему шагу цикла
prices_copy[sell] = 0
pass
# если максимальная цена стоит после минимальной — останавливаем цикл, мы нашли то, что хотели
else:
break
# выводим результаты
print('Покупка: на ' + str(minIndex+1) + ' день по цене ' + str(prices[minBuy]))
print('Продажа: на ' + str(sell+1) + ' день по цене ' + str(prices_copy[sell]))
print('Прибыль — ' +str(profit))
