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).

&nbsp;
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] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.


Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6


&nbsp;
Constraints:


	1 &lt;= prices.length &lt;= 5 * 104
	1 &lt;= prices[i] &lt; 5 * 104
	0 &lt;= fee &lt; 5 * 104


class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        lookup = {}
        def f(ind, buy, lookup):
            
            if ind == n: return 0
            
            if (ind, buy) in lookup: return lookup[(ind, buy)]
            profit = 0
            if buy:
                profit = max(-prices[ind] + f(ind+1,0,lookup), f(ind+1, 1,lookup))
            else:
                profit = max(prices[ind] + f(ind+1,1,lookup) - fee, f(ind+1, 0,lookup))
                
            lookup[(ind,buy)] = profit
            return lookup[(ind,buy)]
        
        return f(0, 1,lookup)
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        for (int[] a : dp) {
            a[0] = -1;
            a[1] = -1;
        }
        return profit(prices, fee, 0, 1, dp);
    }
    public int profit(int[] prices, int fee, int i, int buy, int[][] dp) {
        if (i == prices.length) {
            return 0;
        }
        if (dp[i][buy] != -1) {
            return dp[i][buy];
        }
        int maxProfit = 0;
        if (buy == 1) {
            int yesBuy = profit(prices, fee, i + 1, 0, dp) - prices[i];
            int noBuy = profit(prices, fee, i + 1, 1, dp);
            maxProfit = Math.max(yesBuy, noBuy);
        } else {
            int yesSell = prices[i] - fee + profit(prices, fee, i + 1, 1, dp);
            int noSell = profit(prices, fee, i + 1, 0, dp);
            maxProfit = Math.max(yesSell, noSell);
        }
        return dp[i][buy] = maxProfit;
    }
}
 class Solution {
public:
    int ans=0;
    int f(vector<int>&prices,int i,int buy,vector<vector<int>>&dp,int fee){
        if(i==prices.size())return 0;
        if(dp[i][buy]!=-1)return dp[i][buy];
        int take=0;
        if(buy){
            take=max(-prices[i]+f(prices,i+1,0,dp,fee),f(prices,i+1,1,dp,fee));
        }
        else{
            take=max(prices[i]+f(prices,i+1,1,dp,fee)-fee,f(prices,i+1,0,dp,fee));
        }return dp[i][buy]=take;
    }
    int maxProfit(vector<int>& prices, int fee) {
         vector<vector<int>>dp(prices.size(),vector<int>(2,-1));
        return f(prices,0,1,dp,fee);
    }
};
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let purchase = -1*prices[0];//If we purchase on 0th day
    let sell=0;//If we sell on 0th day
    let prevPurchase;
    for(let i=1;i<prices.length;i++){
        prevPurchase = purchase;
        purchase = Math.max(purchase,sell-prices[i]);//If we purchase on ith day
        sell = Math.max(sell,prevPurchase+prices[i]-fee);//If we sell on ith day
    }
    return sell;//If must return the best price whenever we sold stock because then only we can be at max profit.
};
Best Time to Buy and Sell Stock with Transaction Fee