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

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

• new solution update 2022.03.10

c++

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int profit = 0, n = prices.size(), sellMax = 0, sell;
        for(int i = n - 1; i >= 0; i--) {
            sell = sellMax;
            sellMax = max(sellMax, profit + prices[i] - fee);
            profit = max(profit, sell - prices[i]);
        }
        
        return profit;
    }
};

• new solution update 2022.02.08

c++

class Solution {
    int dp[50001][2];
    int dfs(vector<int>& prices, int i, int& fee, bool hasStock) {
        if(i >= prices.size()) return 0;
        if(dp[i][hasStock] != -1) return dp[i][hasStock];
        if(hasStock) {
            dp[i][hasStock] = max(dfs(prices, i + 1, fee, hasStock), prices[i] + dfs(prices, i + 1, fee, !hasStock));
        } else {
            dp[i][hasStock] = max(dfs(prices, i + 1, fee, hasStock), dfs(prices, i + 1, fee, !hasStock) - prices[i] - fee);
        }
        return dp[i][hasStock];
    }
public:
    int maxProfit(vector<int>& prices, int fee) {
        memset(dp, -1, sizeof(dp));
        return dfs(prices, 0, fee, false);
    }
};

c++

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<pair<int, int>> dp(prices.size(), {0, -prices[0]});

        for(int i = 1; i < prices.size(); i++) {
            dp[i] = {max(dp[i - 1].first, dp[i - 1].second + prices[i] - fee),max(dp[i - 1].second, dp[i - 1].first - prices[i])};
        }

        return max(dp[prices.size() - 1].first, dp[prices.size() - 1].second);
    }
};