To solve this problem, we need to determine the maximum profit that can be achieved from stock trading with a transaction fee for each sale. The key insight is to use dynamic programming to track two states: holding a stock or not holding a stock at each day.

Approach

We use two variables to keep track of the maximum profit for the two states:

1. hold: Maximum profit when holding a stock on the current day.
2. not_hold: Maximum profit when not holding a stock on the current day.

Transitions:

• hold: Either we continue holding the stock from the previous day, or we buy the stock on the current day (subtracting the stock price from the profit of not holding the previous day).
• not_hold: Either we continue not holding the stock from the previous day, or we sell the stock on the current day (adding the stock price minus the transaction fee to the profit of holding the previous day).

Initialization:

• hold starts as -prices[0] (since we buy the stock on the first day).
• not_hold starts as 0 (no stock held initially).

Solution Code

def maxProfit(prices, fee):
    if not prices:
        return 0
    hold = -prices[0]
    not_hold = 0
    for price in prices[1:]:
        new_hold = max(hold, not_hold - price)
        new_not_hold = max(not_hold, hold + price - fee)
        hold, not_hold = new_hold, new_not_hold
    return not_hold

Explanation

Let’s break down the solution using an example:

• Example: prices = [1,3,2,8,4,9], fee = 2.
  • Day 0: hold = -1, not_hold = 0.
  • Day1: hold = max(-1, -3) = -1, not_hold = max(0, -1+3-2=0) =0.
  • Day2: hold = max(-1, -2)= -1, not_hold = max(0, -1+2-2=-1)=0.
  • Day3: hold = max(-1, -8)= -1, not_hold = max(0, -1+8-2=5)=5.
  • Day4: hold = max(-1,5-4=1)=1, not_hold = max(5, -1+4-2=1)=5.
  • Day5: hold = max(1,5-9=-4)=1, not_hold = max(5,1+9-2=8)=8.

The final result is 8, which is the maximum profit achievable.

This approach efficiently computes the result in O(n) time complexity (where n is the number of days) and O(1) space complexity, making it optimal for large input sizes.

Answer: The code returns the maximum profit as required. For the example given, the answer is 8.

\boxed{8}

作者声明:本文包含人工智能生成内容。