# -*- coding: utf-8 -*-
# @Author  : LG

"""
执行用时：52 ms, 在所有 Python3 提交中击败了76.60% 的用户
内存消耗：14.3 MB, 在所有 Python3 提交中击败了10.86% 的用户

解题思路：
    动态规划
    在处理该问题时，主要存在三种状态，买， 卖， 冷冻期。必须在不持有情况下才可以买进，在持有状态下才可以卖出。
    将该问题分为以下三种情况：
        1. 不持有股票
            可以为前一天不持有，或前一天持有卖出
        2. 持有股票
            可以为前一天持有，或前一天为冷冻期，今天买入
        3. 冷冻期
            冷冻期为早一天刚出售股票，今天不能买入，此时利润与前一天不持有时相同。
                * 若早一天不持有是由再前一天不持有状态而来，那么利润不会有变化，所以可以同一逻辑处理。

"""
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        dp = [[0 for _ in range(3)] for _ in range(n)]
        dp[0][1] = -prices[0]               # 第一天持有
        dp[1][0] = max(dp[0][0], dp[0][1]+prices[1])    # 第二天不持有：(第一天不持有， 第一天持有卖出)
        dp[1][1] = max(dp[0][1], dp[0][0]-prices[1])    # 第二天持有：(第一天持有，第一天不持有买进)
        dp[1][2] = dp[0][0]                             # 冷却期当天，利润与前一天不持有股票利润一致
        for i in range(2, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])      # 不持有股票的情况：(原本不持有，早一天持有卖出)
            dp[i][1] = max(dp[i-1][1], dp[i-1][2] - prices[i])      # 持有股票的情况：(原本持有，原本不持有买进，需要注意的是买进时，必须是冷冻期之后才可以)
            dp[i][2] = dp[i-1][0]                                   # 冷冻期与前一天不持有时利润一致
        return max(dp[-1])
