Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

Дан массив целых чисел prices, где prices[i] — цена акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую можно получить, совершив не более k транзакций (одна транзакция = покупка + продажа).
Нельзя участвовать в нескольких транзакциях одновременно — нужно сначала продать акцию, прежде чем покупать новую.

Пример:

Input: k = 2, prices = [2,4,1] Output: 2

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

1⃣Инициализация DP массива
Создаем 3D массив dp[i][j][l], где:
i — день,
j — количество доступных транзакций,
l — держим акцию (1) или нет (0).
Базовые значения: dp[0][0][0] = 0, dp[0][1][1] = -prices[0].

2⃣Переходы состояний
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) — максимальная прибыль без акции.
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) — максимальная прибыль с акцией.

3⃣Оптимизация при большом k
Если k * 2 >= n, можно совершать сделки каждый день — используем жадный подсчет всех выгодных дней.

Решение:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();

        if (n <= 0 || k <= 0) {
            return 0;
        }

        if (k * 2 >= n) {
            int res = 0;
            for (int i = 1; i < n; i++) {
                res += max(0, prices[i] - prices[i - 1]);
            }
            return res;
        }

        vector<vector<vector<int>>> dp(
            n, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = INT_MIN / 2;
                dp[i][j][1] = INT_MIN / 2;
            }
        }

        dp[0][0][0] = 0;
        dp[0][1][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                if (j > 0) {
                    dp[i][j][1] =
                        max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= k; j++) {
            res = max(res, dp[n - 1][j][0]);
        }

        return res;
    }
};

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