Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.

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

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

👨‍💻 Алгоритм:

1⃣Наивный способ — разделить массив на две части и в каждой найти ошибку.
Но он потратил O(n²) времени, так как мы заново просматриваем массив для разделения каждой точки.

2⃣Оптимизируем с помощью динамического программирования:
создаём два массива:
leftProfits[i]— максимальная прибыль от 0 до i
rightProfits[i]— максимальная прибыль от i до конца.
Этот подход уменьшает сложность до O(n).

3⃣После расчета двух массивов суммируемая прибыль из левой и правой частей по каждому соединению:
maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i+1])

😎 Решение:

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        int[] leftProfits = new int[length];
        int[] rightProfits = new int[length + 1];

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = Math.max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = Math.min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = Math.max(
                rightProfits[r + 1],
                rightMax - prices[r]
            );
            rightMax = Math.max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = Math.max(
                maxProfit,
                leftProfits[i] + rightProfits[i + 1]
            );
        }
        return maxProfit;
    }
}

Ставь 👍 и забирай 📚 Базу знаний