Welcome to Subscribe On Youtube
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].
-
public class Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee { public static void main(String[] args) { Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee out = new Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee(); Solution_1D s = out.new Solution_1D(); System.out.println(s.maxProfit(new int[]{1, 3, 2, 8, 12, 15, 4, 9}, 2)); // System.out.println(s.maxProfit(new int[]{1, 3, 2, 8}, 2)); } class Solution_1D { public int maxProfit(int[] prices, int fee) { // what if fee is negative? if (prices == null || prices.length == 0) { return 0; } // sell[i]表示第i天卖掉股票此时的最大利润，hold[i]表示第i天保留手里的股票此时的最大利润 int[] hold = new int[prices.length]; int[] sell = new int[prices.length]; hold[0] = -prices[0]; for (int i = 1; i < prices.length; i++) { hold[i] = Math.max(hold[i - 1], sell[i - 1] - prices[i]); // 前一天sell，今天就要buy，所以减今天的price sell[i] = Math.max(sell[i - 1], hold[i - 1] + prices[i] - fee); // // 前一天buy，今天就要sell，所以加今天的price } return sell[prices.length - 1]; } } class Solution { public int maxProfit(int[] prices, int fee) { // what if fee is negative? if (prices == null || prices.length == 0) { return 0; } int cash = 0, hold = -prices[0]; for (int i = 1; i < prices.length; i++) { //cash in day i is the maxvalue of cash in day i-1 or you sell your stock cash = Math.max(cash, hold + prices[i] - fee); hold = Math.max(hold, cash - prices[i]); } return cash; } } // ref: http://blog.csdn.net/zarlove/article/details/78323469 // 关键是找到一个最大后是不是能够卖掉stock，重新开始寻找买入机会 class Solution_Greedy { public int maxProfit(int[] prices, int fee) { if (prices == null || prices.length == 0) { return 0; } int max = 0; int current = 0; int maxTmp = prices[0]; int minTmp = prices[0]; for (int i = 1; i < prices.length; i++) { maxTmp = Math.max(maxTmp, prices[i]); minTmp = Math.min(minTmp, prices[i]); current = Math.max(current, prices[i] - minTmp - fee); //can just sell the stock at maxP day. if (maxTmp - prices[i] >= fee) { max += current; // reset current = 0; maxTmp = prices[i]; minTmp = prices[i]; } } return max + current; } } } 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]); } } ############ class Solution { public int maxProfit(int[] prices, int fee) { int f1 = -prices[0], f2 = 0; for (int i = 1; i < prices.length; ++i) { f1 = Math.max(f1, f2 - prices[i]); f2 = Math.max(f2, f1 + prices[i] - fee); } return f2; } } -
// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ // Time: O(N) // Space: O(N) class Solution { public: int maxProfit(vector<int>& A, int fee) { if (A.empty()) return 0; int N = A.size(), buy = INT_MIN; vector<int> dp(N + 1); for (int i = 0; i < N; ++i) { buy = max(buy, dp[i] - A[i]); dp[i + 1] = max(dp[i], A[i] - fee + buy); } return dp[N]; } }; -
class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: f1, f2 = -prices[0], 0 for price in prices[1:]: f1 = max(f1, f2 - price) f2 = max(f2, f1 + price - fee) return f2 ############ class Solution: def maxProfit(self, prices, fee): """ :type prices: List[int] :type fee: int :rtype: int """ cash = 0 hold = -prices[0] for i in range(1, len(prices)): cash = max(cash, hold + prices[i] - fee) hold = max(hold, cash - prices[i]) return cash -
func maxProfit(prices []int, fee int) int { f1, f2 := -prices[0], 0 for i := 1; i < len(prices); i++ { f1 = max(f1, f2-prices[i]) f2 = max(f2, f1+prices[i]-fee) } return f2 } func max(a, b int) int { if a > b { return a } return b }