r"""
给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来计算你所能获取的最大利润，你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第4天（股票价格 = 0）的时候买入，在第6天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。
     随后，在第7天（股票价格 = 1）的时候买入，在第8天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第1天（股票价格 = 1）的时候买入，在第5天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。   
     注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为0。

示例 4：

输入：prices = [1]
输出：0
 
提示：
(1) 1 <= prices.length <= 105
(2) 0 <= prices[i] <= 105
"""
import numpy as np


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = np.zeros((n + 1, 2 + 1, 2))
        dp[0, :, 0] = 0
        dp[0, :, 1] = -sys.maxsize
        dp[:, 0, 0] = 0
        dp[:, 0, 1] = -sys.maxsize
        for i in range(1, n + 1):
            for j in range(2, 0, -1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1])
        return int(dp[n][2][0])
