LWC 55：714. Best Time to Buy and Sell Stock with Transaction Fee

LWC 55：714. Best Time to Buy and Sell Stock with Transaction Fee

传送门：714. Best Time to Buy and Sell Stock with Transaction Fee

Problem:

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.

思路： 动态规划，对于每一个可能的买入点都有三种状态：买，卖，什么都不做，枚举出这些状态的组合，求最大profit即可。

目标：

• 前i天的持有股票数最大，记为：hold[i]
• 前i天的股票利益最大，记为：unHold[i]

状态转移：

对于第i + 1天，三种状态，买，卖，什么都不做。

买： hold[i] = max{unHold[i] - prices[i + 1] - fee, hold[i - 1]; 卖：unHold[i] = max{hold[i] + prices[i + 1], unHold[i - 1];

代码如下：

     public int maxProfit(int[] prices, int fee) {
         int n = prices.length;
         int[] hold   = new int[n + 1];
         int[] unHold = new int[n + 1];

         hold[0] = Integer.MIN_VALUE;

         for (int i = 1; i <= n; ++i) {
             hold[i]   = Math.max(hold[i - 1], unHold[i - 1] - prices[i - 1] - fee);
             unHold[i] = Math.max(unHold[i - 1], hold[i - 1] + prices[i - 1]);
         }

         return unHold[n];
     }