714. Лучшее время для покупки и продажи акций с комиссией за транзакцию (Best Time to Buy and Sell Stock with Transaction Fee)
Задание.
Вам предоставляется массив prices, где prices[i] – это цена данной акции на i-й день, а также целочисленное fee, представляющее комиссию за транзакцию.
Найдите максимальную прибыль, которой вы можете достичь. Вы можете совершать столько транзакций, сколько захотите, однако за каждую транзакцию вам необходимо оплатить комиссию.
Примечание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е. вы должны продать акции, прежде чем покупать снова).
Пример 1.
Входные данные: prices = [1,3,2,8,4,9], fee = 2
Результат: 8
Объяснение:
Максимальная прибыль может быть достигнута за счет:
-
Покупка по prices[0] = 1
-
Продажа по prices[3] = 8
-
Покупка по prices[4] = 4
-
Продажа по prices[5] = 9
Общая прибыль составляет ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Пример 2.
Входные данные: prices = [1,3,7,5,10,3], fee = 3
Результат: 6
Решение.
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int days = prices.size();
if (days <= 1) return 0;
vector<int> buy(days, 0);
vector<int> sell(days, 0);
buy[0] = -prices[0];
for (int i = 1; i < days; i++) {
buy[i] = max(buy[i - 1], sell[i - 1] - prices[i]);
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i] - fee);
}
return sell[days - 1];
}
};