To solve this problem, we need to determine the maximum profit that can be obtained from buying and selling stocks multiple times, considering a transaction fee for each sale. The optimal approach uses dynamic programming with space optimization to efficiently compute the result.

Approach

The problem can be efficiently solved using dynamic programming (DP) with two states to track the maximum profit at each day:

1. Hold: The maximum profit if we hold a stock at the end of the day.
2. Not Hold: The maximum profit if we do not hold any stock at the end of the day.

State Transitions:

• Hold: Either we keep holding the stock from the previous day or we buy a new stock on the current day (using the profit from not holding on the previous day minus the current stock price).

  • hold[i] = max(hold[i-1], not_hold[i-1] - prices[i])

• Not Hold: Either we keep not holding the stock from the previous day or we sell the stock we held on the previous day (adding the current stock price minus the transaction fee to the profit from holding on the previous day).

  • not_hold[i] = max(not_hold[i-1], hold[i-1] + prices[i] - fee)

Space Optimization:

We don't need to maintain an array for all days. Instead, we use two variables (hold and not_hold) to track the state values from the previous day, reducing the space complexity to O(1).

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

1. Initialization:

   • hold starts as -prices[0] because we buy the stock on the first day.
   • not_hold starts as 0 because we have no stock and no profit initially.

2. Iterate Through Prices:

   • For each subsequent day, compute the new values of hold and not_hold using the transitions mentioned earlier.
   • Update the previous state variables to the new values for the next iteration.

3. Result:

   • The maximum profit is the value of not_hold at the end of the iteration, as holding a stock on the last day does not contribute to profit (we need to sell all stocks to realize gains).

This approach runs in O(n) time complexity (where n is the number of days) and O(1) space complexity, making it optimal for large input sizes. It efficiently handles all edge cases, including empty price lists and single-day prices.

Example: For prices = [1,3,2,8,4,9] and fee=2, the function returns 8 (correct as explained earlier). This confirms the solution works as expected.

Final Answer: The function maxProfit as written above is the correct solution. The final answer is the code provided.

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

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。