📈 Максимальная прибыль от многократных сделок с акциями

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

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

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