**Problem link** — https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/↵
↵
**Problem Description:** ↵
↵
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] = 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.↵
↵
**Note:**↵
0 < prices.length <= 50000; ↵
0 < prices[i] < 50000; ↵
0 <= fee < 50000.↵
↵
↵
**My Solution** : I have come up with a backtrack solution, which is working fine with smaller inputs, but gives TLE with bigger inputs. I am unable to memoize it. Need Help !!!↵
↵
What I am doing is, I am checking if the we have already purchased a share, If Yes, either we can sell the share now or later. If No, we either purchase it now or later. ↵
↵
↵
~~~~~↵
class Solution↵
{↵
public:↵
↵
int solve (vector<int> &prices, bool hasPurchased, int lastPurchasedVal, int i, int fee)↵
{↵
if (i == prices.size()) return 0;↵
↵
// if (dp[hasPurchased][i] != -1) return dp[hasPurchased][i];↵
↵
if (hasPurchased)↵
{↵
int sold = INT_MIN;↵
int profit = prices[i] - lastPurchasedVal - fee;↵
if (profit > 0)↵
sold = profit + solve (prices, !hasPurchased, 0, i+1, fee);↵
int notsold = solve(prices, hasPurchased, lastPurchasedVal, i+2, fee);↵
return max(sold, notsold);↵
}↵
else↵
{↵
int purchased = solve (prices, !hasPurchased, prices[i], i+1, fee);↵
int notPurchased = solve(prices, hasPurchased, lastPurchasedVal, i+1, fee);↵
return max(purchased, notPurchased);↵
} ↵
}↵
↵
int maxProfit(vector<int>& prices, int fee) ↵
{↵
//int dp[2][50001];↵
//memset(dp, -1, sizeof dp);↵
return solve (prices, false, 0, 0, fee);↵
}↵
};↵
~~~~~↵
↵
↵
Thank you.↵
↵
**Problem Description:** ↵
↵
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] = 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.↵
↵
**Note:**↵
0 < prices.length <= 50000; ↵
0 < prices[i] < 50000; ↵
0 <= fee < 50000.↵
↵
↵
**My Solution** : I have come up with a backtrack solution, which is working fine with smaller inputs, but gives TLE with bigger inputs. I am unable to memoize it. Need Help !!!↵
↵
What I am doing is, I am checking if the we have already purchased a share, If Yes, either we can sell the share now or later. If No, we either purchase it now or later. ↵
↵
↵
~~~~~↵
class Solution↵
{↵
public:↵
↵
int solve (vector<int> &prices, bool hasPurchased, int lastPurchasedVal, int i, int fee)↵
{↵
if (i == prices.size()) return 0;↵
↵
// if (dp[hasPurchased][i] != -1) return dp[hasPurchased][i];↵
↵
if (hasPurchased)↵
{↵
int sold = INT_MIN;↵
int profit = prices[i] - lastPurchasedVal - fee;↵
if (profit > 0)↵
sold = profit + solve (prices, !hasPurchased, 0, i+1, fee);↵
int notsold = solve(prices, hasPurchased, lastPurchasedVal, i+2, fee);↵
return max(sold, notsold);↵
}↵
else↵
{↵
int purchased = solve (prices, !hasPurchased, prices[i], i+1, fee);↵
int notPurchased = solve(prices, hasPurchased, lastPurchasedVal, i+1, fee);↵
return max(purchased, notPurchased);↵
} ↵
}↵
↵
int maxProfit(vector<int>& prices, int fee) ↵
{↵
//int dp[2][50001];↵
//memset(dp, -1, sizeof dp);↵
return solve (prices, false, 0, 0, fee);↵
}↵
};↵
~~~~~↵
↵
↵
Thank you.↵