from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length <= 1:return 0
        dp=[ [[0,0,0],[0,0,0] ] for i in range(0,length) ]
        # 第一天不买入
        dp[0][0][0] = 0
        # 第一天不买入
        dp[0][1][0] = -prices[0]
        # 第一天不可能有卖出
        dp[0][0][2] = float("-inf")
        dp[0][0][1] = float("-inf")
        # 第一天同样不可能即持股，又卖出
        dp[0][1][2] = float("-inf")
        dp[0][1][1] = float("-inf")
        for index in range(1,length):
            # 没有持股和卖出，利润为0
            dp[index][0][0] = 0
            # 持股不卖出，有可能是今天持股，有可能昨天已经持股
            dp[index][1][0] = max(dp[index - 1][0][0] - prices[index],dp[index - 1][1][0])
            # 今天没有股票且卖出两次，有可能是今天卖出，也有可能是昨天就卖出
            dp[index][0][2] = max(prices[index] + dp[index - 1][1][1],dp[index - 1][0][2])
            # 今天没有股票且卖出一次，有可能是今天卖出，也有可能是昨天卖出
            dp[index][0][1] = max(prices[index] + dp[index - 1][1][0],dp[index - 1][0][1])
            # 今天有股票且卖出一次，有可能是今天买入，有可能是昨天就买入
            dp[index][1][1] = max(dp[index - 1][0][1] - prices[index],dp[index - 1][1][1])
            # 今天有股票且卖出两次，不可能
            dp[index][1][2] = float("-inf")
        print(dp)
        return max(dp[-1][0][2],dp[-1][0][1],dp[-1][0][0])
    # 通过正序和逆序遍历求出两个最大利润，然后相加找出最大的那个。
    # 第二个答案不是很懂，不知道怎么证明其正确性
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length <= 1:return 0
        min_price,max_price = prices[0],prices[-1]
        profit1,profit2 = [0] * length,[0] * length
        for index in range(1,length):
            min_price = min(min_price,prices[index])
            profit1[index] = max(profit1[index - 1],prices[index] - min_price)

            max_price = max(max_price,prices[length - 1 - index])
            profit2[length - index - 1] = max(profit2[length - index],max_price - prices[length - index - 1])

        profit = profit1[-1]
        for index in range(length):
            profit = max(profit1[index] + profit2[index],profit)
        return profit


A = Solution()
print(A.maxProfit([3,3,5,0,0,3,1,4]))
print(A.maxProfit([1,2,3,4,5]))