Leetcode123 timing of buying and selling stocks III

difficulty ： difficult

Title Description

Power button ​​​​​​

Ideas

Dynamic programming

Power button

1） Define the State

No operation ; Buy only once buy1; Carry out a buy and sell operation , That is to complete a transaction sell1; Make a second purchase buy2; Complete two transactions sell2.

2） Transfer equation

The first i Days without operation , Or i-1 Days without operation , The first i Heaven and earth prices[i] Buy stock at a price

buy1​=max{buy1′​,−prices[i]}=max{buy1,−prices[i]}

The first i Days without operation , Or i-1 Only buy everyday , The first i Heaven and earth prices[i] Sell shares at a price

sell1​=max{sell1′​,buy1′​+prices[i]}=max{sell1,buy1+prices[i]}

The first i Days without operation , Or i-1 Complete a transaction in days , The first i Heaven and earth prices[i] Buy stock at a price

buy2=max{buy2′,sell1′−prices[i]}=max{buy2,sell1−prices[i]}

The first i Days without operation , Or i-1 Day for the second time to buy , The first i Heaven and earth prices[i] Sell shares at a price

sell2=max{sell2′,buy2′+prices[i]}=max{sell2,buy2+prices[i]}

3） The initial state

buy1​=−prices[0];sell1=0;buy2=−prices[0];sell2=0

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        return sell2

 author ：LeetCode-Solution
 link ：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .