0

Условие: Мистер Твистер, банкир и финансист, имеет доступ к секретным материалам - курс местной денежной валюты на N дней вперёд. Как человек, везде старающийся найти выгоду, мистер Твистер поставил перед собой задачу - необходимо выбрать день, когда нужно купить эту самую валюту и когда её нужно продать, чтобы получить максимальную прибыль.

Формат ввода: В первой строке вводится число N — количество дней, на которые известен курс валюты. Во второй строке находится N чисел — стоимость валюты в рублях в соответствующий день.

Формат вывода: Требуется вывести два числа — день, когда нужно купить валюту и день, когда нужно её продать, чтобы получить максимальную прибыль. Причем если способов выбрать эту пару дней несколько, то нужно выбрать тот, при котором мистер Твистер сможет сбыть валюту с рук. Если же и таких пар несколько, то нужно учесть тот же принцип - чем раньше, тем лучше. Если же в эти дней покупать и продавать валюту будет невыгодно или бесполезно, то выведите -1.

Пример: Ввод: 5 1 2 1 5 3 Вывод: 3 4

Ввод: 3 200 100 50 Вывод:

Потуги моих рассуждений: я осознал лишь, что если на всём промежутке следующее число меньше предыдущего, то акции падают и нужно выводить -1. (0 добавил для того, чтобы избежать index out of range)

n = int(input())
term = list(map(int, input().split()))
term.append(0)
if not any(term[i] < term[i + 1] for i in range(n)):
    print(-1)

Дальше просто впадаю в ступор. Задача кажется знакомой, возможно, её условие популярно на олимпиадах. Однако, какой алгоритм? Если идти по всему списку и итератором отслеживать, когда следующее число меньше, а когда больше предыдущего, то это долго, затратно по памяти, да и не факт, что логика сработает. Был вариант искать индексы вхождений максимального и минимального числа, чтобы сравнивать их позиции, но если максимум стоит перед минимумом, то что дальше? Если кто-то сталкивался с аналогией, можете объяснить принцип, пожалуйста?

3
  • Тупой алгоритм в лоб: для каждой пары дней i и j (i<j) ищем сколько заработаем, если купить в день i и продать в j. Выбираем пару, где заработаем максимум. 4 мая 2021 в 14:18
  • Заголовок исправьте на имеющий отношение к проблеме.
    – MBo
    5 мая 2021 в 14:10
  • В задаче нигде не упомянуто, что покупать надо до продажи. Это подразумевается или нет? 5 мая 2021 в 14:26

1 ответ 1

0

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

for x in term:
    bestprofit = max(bestprofit, x - minsofar)
    minsofar = min(minsofar, x)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.