Formatted question description: https://leetcode.ca/all/714.html

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

## Level

Medium

## Description

You 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`

.

## Solution

Use dynamic programming. For each day, there are four possible operations.

- Buy the stock. This operation can be done only when no stock is at hand.
- Keep the stock. This operation can be done only when the stock is bought and not sold.
- Sell the stock. This operation can be done only when the stock is bought and not sold.
- Keep empty hand. This operation can be done only when no stock is at hand.

Let `length`

be `prices.length`

. Create a 2D array `dp`

of `length`

rows and 4 columns, where `dp[i][j]`

represents the maximum profit on the `i`

-th day when selecting the `j`

-th operation (`j`

ranges from 0 to 3, which corresponds to the operation 1 to 4 respectively).

For day 0, it is not possible to sell the stock, and if keeping empty hand, the profit is 0, so set `dp[0][2] = 0`

and `dp[0][3] = 0`

. If buying the stock, then the profit is `-prices[0]`

, so set `dp[0][0] = -prices[0]`

. Although it is impossible to keep the stock before buying the stock, the meaning of keeping the stock is the same as the meaning of buying the stock for day 0, so set `dp[0][1] = -prices[0]`

as well.

For the rest of the days, update `dp`

as follows.

- Buy the stock. This operation can be done only if the previous operation was to sell the stock or to keep empty hand, so set
`dp[i][0] = Math.max(dp[i - 1][2], dp[i - 1][3]) - prices[i]`

. - Keep the stock. This operation can be done only if the previous operation was to buy the stock or to keep the stock, so set
`dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1])`

. - Sell the stock. This operation can be done only if the previous operation was to buy the stock or to keep the stock, and a transaction fee needs to be paid when selling the stock, so set
`dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]) + prices[i] - fee`

. - Keep empty hand. This operation can be done only if the previous operation was to sell the stock or to keep empty hand, so set
`dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3])`

.

Finally, to make the maximum profit, the stock must be sold, which means on the last day, buying the stock or keeping the stock will not lead to the optimal solution. Therefore, return the maximum of `dp[length - 1][2]`

and `dp[length - 1][3]`

.

Java

```
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length <= 1)
return 0;
int length = prices.length;
int[][] dp = new int[length][4];
dp[0][0] = -prices[0];
dp[0][1] = -prices[0];
for (int i = 1; i < length; i++) {
dp[i][0] = Math.max(dp[i - 1][2], dp[i - 1][3]) - prices[i];
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]) + prices[i] - fee;
dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3]);
}
return Math.max(dp[length - 1][2], dp[length - 1][3]);
}
}
```