📈 Максимальная прибыль с ограничением в две сделки (leetcode 12

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

Речь о сложной задаче 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 моделирует реальные ситуации, когда брокерские ограничения или комиссии делают частые сделки невыгодными, и инвестор вынужден тщательно выбирать несколько ключевых моментов для торговли.