题目

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

  1. Input: prices = [1,3,2,8,4,9], fee = 2
  2. Output: 8
  3. Explanation: The maximum profit can be achieved by:
  4. - Buying at prices[0] = 1
  5. - Selling at prices[3] = 8
  6. - Buying at prices[4] = 4
  7. - Selling at prices[5] = 9
  8. The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

  1. Input: prices = [1,3,7,5,10,3], fee = 3
  2. Output: 6

Constraints:

  • 1 < prices.length <= 5 * 10^4
  • 0 < prices[i], fee < 5 * 10^4

题意

股票买卖问题。给定每一天的股票价格以及相应规则：同一天只能买或卖，卖股票必须在买股票之后，可以执行多次买卖交易，但每次卖股票后要扣除一定的手续费。

思路

和 0309. Best Time to Buy and Sell Stock with Cooldown (M) 解法基本一致。动态规划解决。

代码实现

Java

  1. class Solution {
  2.     public int maxProfit(int[] prices, int fee) {
  3.         int[] hold = new int[prices.length];
  4.         int[] sold = new int[prices.length];
  6.         hold[0] = -prices[0];
  7.         sold[0] = 0;
  9.         for (int i = 1; i < prices.length; i++) {
  10.             hold[i] = Math.max(hold[i - 1], sold[i - 1] - prices[i]);
  11.             sold[i] = Math.max(sold[i - 1], hold[i - 1] + prices[i] - fee);
  12.         }
  14.         return sold[prices.length - 1];
  15.     }
  16. }