<p>You are given an array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day.</p>

<p>Find the maximum profit you can achieve. You may complete <strong>at most two transactions</strong>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [3,3,5,0,0,3,1,4]
<strong>Output:</strong> 6
<strong>Explanation:</strong> Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,2,3,4,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> prices = [7,6,4,3,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> In this case, no transaction is done, i.e. max profit = 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= prices[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        N = len(prices)
        memo = [[-prices[0], 0, -prices[0], 0] for _ in range(N)]

        for i in range(1, N):
            memo[i][0] = max(memo[i - 1][0], -prices[i])
            memo[i][1] = max(memo[i - 1][1], memo[i - 1][0] + prices[i])
            memo[i][2] = max(memo[i - 1][2], memo[i - 1][1] - prices[i])
            memo[i][3] = max(memo[i - 1][3], memo[i - 1][2] + prices[i])

        return memo[-1][-1]
        

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        def helper(k: int, prices: List[int]) -> int:
            if not prices or k == 0: return 0
            N = len(prices)
            memo = [[0 for _ in range(2 * k)] for _ in range(N)]
            for i in range(0, 2 * k, 2):
                memo[0][i] = -prices[0]

            for i in range(1, N):
                for j in range(0, 2 * k, 2):
                    memo[i][j] = max(memo[i - 1][j], (memo[i - 1][j - 1] if j > 0 else 0) - prices[i])
                    memo[i][j + 1] = max(memo[i - 1][j + 1], memo[i - 1][j] + prices[i])

            return memo[-1][-1]

        return helper(2, prices)


from functools import cache
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)

        @cache
        def dp(idx: int) -> (int, int, int, int):
            if idx == 0:
                return (-prices[0], 0, -prices[0], 0)

            prev_w1, prev_wo1, prev_w2, prev_wo2 = dp(idx - 1)

            # 第一次交易后的持有状态
            w1 = max(prev_w1, -prices[idx])
            # 第一次交易后的不持有状态
            wo1 = max(prev_wo1, prev_w1 + prices[idx])
            # 第二次交易后的持有状态
            w2 = max(prev_w2, prev_wo1 - prices[idx])
            # 第二次交易后的不持有状态
            wo2 = max(prev_wo2, prev_w2 + prices[idx])

            return w1, wo1, w2, wo2

        return dp(N - 1)[-1]


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)

        memo = {0: (-prices[0], 0, -prices[0], 0)}
        def dp(idx: int) -> (int, int, int, int):
            if idx in memo:
                return memo[idx]

            prev_w1, prev_wo1, prev_w2, prev_wo2 = dp(idx - 1)

            # 第一次交易后的持有状态
            w1 = max(prev_w1, -prices[idx])
            # 第一次交易后的不持有状态
            wo1 = max(prev_wo1, prev_w1 + prices[idx])
            # 第二次交易后的持有状态
            w2 = max(prev_w2, prev_wo1 - prices[idx])
            # 第二次交易后的不持有状态
            wo2 = max(prev_wo2, prev_w2 + prices[idx])

            memo[idx] = w1, wo1, w2, wo2
            return memo[idx]

        return dp(N - 1)[-1]

154251