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

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

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.

1. Buy the stock. This operation can be done only when no stock is at hand.
2. Keep the stock. This operation can be done only when the stock is bought and not sold.
3. Sell the stock. This operation can be done only when the stock is bought and not sold.
4. 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.

1. 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].
2. 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]).
3. 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.
4. 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]);
}
}