Сайт: https://easyoffer.ru/
Все каналы: t.me/+xGeAw6ckJ4liYzQy
Контакт для рекламы: @sendme_ads
Post #1900
327
Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard
Дан массив целых чисел prices, где prices[i] — цена акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую можно получить, совершив не более k транзакций (одна транзакция = покупка + продажа).
Нельзя участвовать в нескольких транзакциях одновременно — нужно сначала продать акцию, прежде чем покупать новую.
Пример:
👨💻 Алгоритм:
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, можно совершать сделки каждый день — используем жадный подсчет всех выгодных дней.
Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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;
}
};Ставь 👍 и забирай 📚 Базу знаний
