亚洲精品不卡AV在线播放|国产性爱无码高清视频|国产成人 ,97人人色,国产免费一区二区三区,日本一区二区在线

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

（免責(zé)聲明：本文為本網(wǎng)站出于傳播商業(yè)信息之目的進(jìn)行轉(zhuǎn)載發(fā)布，不代表本網(wǎng)站的觀點(diǎn)及立場(chǎng)。本文所涉文、圖、音視頻等資料的一切權(quán)利和法律責(zé)任歸材料提供方所有和承擔(dān)。本網(wǎng)站對(duì)此資訊文字、圖片等所有信息的真實(shí)性不作任何保證或承諾，亦不構(gòu)成任何購(gòu)買、投資等建議，據(jù)此操作者風(fēng)險(xiǎn)自擔(dān)。） 本文為轉(zhuǎn)載內(nèi)容，授權(quán)事宜請(qǐng)聯(lián)系原著作權(quán)人，如有侵權(quán)，請(qǐng)聯(lián)系本網(wǎng)進(jìn)行刪除。