"""
给定一个数组，它的第 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


from typing import *


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ## 最简单的分治法，复用了121的代码，时间复杂度为O(n^2)，能过大部分的测试样例（201/214）
        # def subMaxProfit(prices: List[int]) -> int:
        #     if len(prices) < 2:
        #         return 0
        #     cur_min, max_profit = prices[0], 0
        #     for p in prices[1:]:
        #         cur_profit = p - cur_min
        #         max_profit = cur_profit if cur_profit > max_profit else max_profit
        #         cur_min = p if p < cur_min else cur_min
        #     return max_profit

        # max_profit = 0
        # for i in range(len(prices)-1):
        #     cur_profit = subMaxProfit(prices[:i]) + subMaxProfit(prices[i:])
        #     max_profit = cur_profit if cur_profit > max_profit else max_profit

        # return max_profit

        ## 动态规划，时间复杂度为O(N)
        if len(prices) < 2:
            return 0

        # 动规数组，dp1[i] 表示以i作为卖出时刻能获得最大收益， dp2[i]表示以i作为买入时刻能获得最大收益，均考虑单次交易
        dp1, dp2 = [0 for _ in range(len(prices))], [0 for _ in range(len(prices))]
        cur_min = prices[0]
        for i in range(len(prices)):
            dp1[i] = 0 if prices[i] < cur_min else prices[i] - cur_min
            cur_min = prices[i] if prices[i] < cur_min else cur_min

        cur_max = prices[-1]
        for i in range(len(prices) - 1, -1, -1):
            dp2[i] = 0 if prices[i] > cur_max else cur_max - prices[i]
            cur_max = prices[i] if prices[i] > cur_max else cur_max

        # 在dp1，dp2的基础上再考虑：pre[i]表示在0~i区间内单次交易可以获得的最大收益，post[i]表示在i~-1区间内交易能获得的最大收益
        pre, post = [0 for _ in range(len(prices))], [0 for _ in range(len(prices))]
        max_profit = dp1[0]
        for i in range(len(prices)):
            pre[i] = dp1[i] if dp1[i] > max_profit else max_profit
            max_profit = pre[i]
        max_profit = dp2[-1]
        for i in range(len(prices) - 1, -1, -1):
            post[i] = dp2[i] if dp2[i] > max_profit else max_profit
            max_profit = post[i]

        # 然后将问题分割成两个子问题：在0~i区间和i+1~-1区间内分别做交易，寻找最大化收益的点即可
        max_profit = 0
        for i in range(len(prices) - 1):
            cur_profit = pre[i] + post[i + 1]
            max_profit = cur_profit if cur_profit > max_profit else max_profit
        max_profit = pre[-1] if pre[-1] > max_profit else max_profit
        return max_profit

