买卖股票的最好时机(三)

到第i天为止的5种状态：

• dp[i][0]表示到第i天为止没有买过股票的最大收益
• dp[i][1]dp[i][1]dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
• dp[i][2]dp[i][2]dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
• dp[i][3]dp[i][3]dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
• dp[i][4]dp[i][4]dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益
  收益可能为负数，可能交易二次的收益大，也可能交易一次收益最大

  class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        res = 0
        n = len(prices)
        dp = [[-10000]*5 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = dp[i-1][0]
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
            dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
        return max(dp[n-1][2], dp[n-1][4], 0)

dp[i][0] = max(dp[i-1][1]+prices[i],dp[i-1][0])

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        length=len(prices)
        if length==0:
            return 0
        dp=[0]*5
        dp[1]=-prices[0]
        dp[3]=-prices[0]
        for i in range(1,len(prices)):
            dp[1]=max(dp[1],dp[0]-prices[i])
            dp[2]=max(dp[2],dp[1]+prices[i])
            dp[3]=max(dp[3],dp[2]-prices[i])
            dp[4]=max(dp[4],dp[3]+prices[i])
        return dp[4]

class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices:
            return 0
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, len(prices)):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, prices[i] + buy1)
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, prices[i] + buy2)
        return sell2
    # 动态规划最初的理解代码————————————————————————————————
#         if len(prices) <= 1:
#             return 0
#         n = len(prices)
#         dp = [[[0] * 2 for _ in range(3)] for _ in range(n) ] 
#         for k in range(3): # 3表示三个状态，分别是rest, sell, buy
#             dp[0][k][1] = -prices[0] # 第0天时，持有的股票收益都是-prices[0]
#         for i in range(1, n): # i表示天数
#             for k in range(1, 3): # k表示次数
#                 dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])#0表示没有持有股票，那就要加上今天的prices
#                 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
#         return dp[n-1][2][0] # n-1表示最后一天，2表示两次交易，0表示手中没有股票

class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices: return 0
        buy1 = -prices[0]
        buy2 = -prices[0]
        sell1, sell2 = 0, 0
        for i in range(1, len(prices)):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1+prices[i])
            buy2 = max(buy2, sell1-prices[i])
            sell2 = max(sell2, buy2+prices[i])
        return sell2