# Best Time to Buy and Sell Stock With Cost

• You can make unlimited transactions, but each sell or buy has a fixed cost. For example:
given the prices [1, 3, 6, 5, 8], cost = 1, the max profit is 5. To see this, you can buy at 1 and sell at 8 to get a profit of 7, minus the transaction cost 2, and the final result is 5.

• Same DP idea as in stock buy and sell with cooldown? We can maintain 4 variables:

``````s_i: max profit so far sell at day i
b_i: max profit so far buy at day i
h_i: max profit so far hold at day i
e_i: max profit so far being lazy at day i
``````

With the following recurrence relation: j denotes i-1 here, cb is buy cost, cs is sell cost, p_i is the price at day i

• s_i = max(b_j, h_j, s_j + cs - p_j) - cs + p_i
• b_i = max(e_j, s_j) - cb - p_i
• h_i = max(h_j, b_j)
• e_i = max(e_j, s_j)

• Thanks for offering this question! My DP idea:

States:
(1) If we are holding the stock at the end of day i, the max possible profit at the end of day i is recorded as: hold[i]
(2) If we are holding nothing at the end of day i, the max possible profit at the end of day i is recorded as: empty[i]

Transition Functions:

``````hold[i] = Math.max(hold[i - 1], empty[i - 1] - prices[i] - buyCost)
empty[i] = Math.max(empty[i - 1], hold[i - 1] + prices[i] - sellCost)
``````

And of course they can be simplified to O(1) space.

• thx @HungryOrc !

With your idea, I finish the code as below, and it is accepted!

``````    // buyCost = 0
public int maxProfit(int[] prices, int fee) {
if(prices == null || prices.length < 2) return 0;

int[] hold = new int[prices.length];
int[] empty = new int[prices.length];
hold[0] = -prices[0];
empty[0] = 0;
for (int i = 1; i < prices.length; i++) {
hold[i] = Math.max(hold[i - 1], empty[i - 1] - prices[i]);
empty[i] = Math.max(empty[i - 1], hold[i - 1] + prices[i] - fee);
}
return empty[prices.length - 1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.