714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

// Dynamic programming
// buy[i] = max(buy[i - 1], sell[i - 1] - prices[i])
// sell[i] = max(sell[i - 1], buy[i - 1] + prices[i] - fee)
int maxProfit(vector<int>& prices, int fee) { // time: O(n); space: O(1)
    long preBuy = INT_MIN, buy = INT_MIN, sell = 0;
    for (int price : prices) {
        preBuy = buy;
        buy = max(buy, sell - price);
        sell = max(sell, preBuy + price - fee);
    }
    return (int)sell;
}

// DP with 1D vector
int maxProfit(vector<int>& prices, int fee) { // time: O(n); space: O(n)
    int n = prices.size();
    if (n <= 1) return 0;
    vector<int> buy(n, 0), sell(n, 0);
    buy[0] = -prices[0];
    for (int i = 1; i < n; ++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.back();
}

// Space-Optimized DP
int maxProfit(vector<int>& prices, int fee) { // time: O(n); space: O(1)
    int n = prices.size();
    if (n <= 1) return 0;
    int buy = -prices[0], sell = 0, preBuy;
    for (int i = 1; i < n; ++i) {
        preBuy = buy;
        buy = max(buy, sell - prices[i]);
        sell = max(sell, preBuy + prices[i] - fee);
    }
    return sell;
}

// Space-Optimized DP
int maxProfit(vector<int>& prices, int fee) { // time: O(n); space: O(1)
    int n = prices.size();
    if (n <= 1) return 0;
    int buy = -prices[0], sell = 0, preSell;
    for (int i = 1; i < n; ++i) {
        preSell = sell;
        sell = max(sell, buy + prices[i] - fee);
        buy = max(buy, preSell - prices[i]);
    }
    return sell;
}

121. Best Time to Buy and Sell Stock122. Best Time to Buy and Sell Stock II123. Best Time to Buy and Sell Stock III188. Best Time to Buy and Sell Stock IV309. Best Time to Buy and Sell Stock with Cooldown