leetcode problems

Допустим, вы стали трейдером на оживлённой фондовой бирже. У вас есть чёткое правило: вы можете совершить не более двух сделок купли-продажи акций за день. Как выбрать оптимальные моменты для покупки и продажи, чтобы получить максимальную прибыль? Эта задача моделирует реальную ситуацию, с которой сталкиваются инвесторы при торговле с ограниченным количеством транзакций.

Речь о сложной задаче 123. Best Time to Buy and Sell Stock III

В задаче необходимо определить две непересекающиеся пары (покупка, продажа), где каждая последующая покупка происходит после продажи предыдущей. При этом суммарная прибыль от этих двух сделок должна быть максимально возможной. Например, для цен [3,3,5,0,0,3,1,4] оптимальные сделки — (0→3) и (1→4) с суммарной прибылью 6.

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

Особенности решения

Задача требует более сложного подхода, чем предыдущие версии. Простое суммирование всех прибыльных отрезков не подойдёт — необходимо:

• Отслеживать потенциальные сделки как до, так и после каждого дня

• Комбинировать наиболее выгодные пары сделок

• Учитывать возможность получения максимальной прибыли всего от одной сделки, если вторая не увеличивает общий доход

Решение эффективно использует динамическое программирование для отслеживания оптимальных стратегий с разным количеством оставшихся сделок.

Алгоритм решения (динамическое программирование)

1. Инициализация: Создаем переменные для отслеживания:

• buy1— минимальная цена после первой покупки

• profit1— максимальная прибыль после первой продажи

• buy2— минимальная цена после второй покупки (с учетом прибыли от первой сделки)

• profit2— общая максимальная прибыль после второй продажи

2. Проход по массиву: Для каждой цены обновляем значения:

text

3. Результат: Возвращаем profit2 — максимальную прибыль после двух сделок.

Python решение

text

Отличие от задачи 122

1. Ограничение на количество сделок: В задаче 122 можно совершать неограниченное количество сделок, тогда как в текущей задаче разрешено не более двух транзакций. Это требует принципиально другого подхода — вместо простого суммирования всех прибыльных отрезков необходимо тщательно выбирать две наиболее выгодные сделки.

2. Сложность алгоритма: Решение задачи 122 имеет линейную сложность O(n) с простой логикой, тогда как задача 123 требует более сложного подхода с динамическим программированием для отслеживания двух потенциальных сделок одновременно, хотя также сохраняет линейную сложность O(n).

3. Результаты: Для цен [3,3,5,0,0,3,1,4]:

• В задаче 122 прибыль составила бы 5 (0→3 и 1→4)

• В задаче 123 прибыль составляет 6 (0→3 и 1→4), так как мы ограничены двумя сделками и выбираем оптимальные

Практическое применение: Задача 123 моделирует реальные ситуации, когда брокерские ограничения или комиссии делают частые сделки невыгодными, и инвестор вынужден тщательно выбирать несколько ключевых моментов для торговли.

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

Эта задача среднего уровня сложности расширяет Leetcode-задачу 122. Best Time to Buy and Sell Stock II

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

А также найти оптимальные точки входа и выхода для каждой отдельной сделки. Хотя явное определение конкретных дней покупки/продажи не требуется для решения, алгоритм по сути находит все локальные минимумы (точки покупки) и следующие за ними локальные максимумы (точки продажи), суммируя прибыль от каждой такой операции.

Отличие от задачи 121 (Best Time to Buy and Sell Stock)

1. Количество сделок: В задаче 121 разрешена только одна операция купли-продажи, тогда как в текущей задаче можно совершать неограниченное количество сделок (с условием владения не более одной акцией одновременно). Это коренным образом меняет подход к решению — вместо поиска единственной максимальной разницы мы собираем все положительные ценовые движения.

2. Сложность решения: Задача 121 требует отслеживания глобального минимума и максимальной разницы после него, в то время как текущая задача решается простым суммированием всех возрастающих соседних значений, что делает алгоритм более прямолинейным и эффективным (хотя и основанным на другом принципе).

3. Результаты: В задаче с одной сделкой максимальная прибыль для [7,1,5,3,6,4] составляет 5 (покупка за 1, продажа за 6), тогда как при многократных сделках мы получаем 7 (1→5 и 3→6), демонстрируя принципиально разные стратегии торговли.

Алгоритм решения (метод "пиков и впадин")

1. Инициализация: Создаем переменную для хранения общей прибыли (totalProfit).

2. Проход по массиву: Для каждого дня, начиная со второго:

• Если цена сегодня выше, чем вчера (prices[i] > prices[i-1]), добавляем разницу к общей прибыли.

1. Результат: Возвращаем накопленную прибыль.

Этот подход работает, потому что мы "собираем" все возрастающие отрезки ценовой кривой, что эквивалентно множественным покупкам и продажам на каждом локальном минимуме и максимуме.

Python решение

text

Ключевые особенности решения

1. Простота и эффективность: Алгоритм проходит по массиву всего один раз, имея временную сложность O(n) и пространственную O(1).

2. Жадный подход: Мы максимизируем прибыль, собирая все возможные положительные разницы между соседними днями.

3. Универсальность: Решение работает для любых ценовых последовательностей, включая монотонно растущие и падающие.

Этот метод идеально подходит для сценариев, где разрешено неограниченное количество сделок, и демонстрирует, как простая стратегия может давать оптимальные результаты на финансовых рынках.