123. 买卖股票的最佳时机 III 难

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

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

太难—人肉想状态转移，边界过于复杂，没必要 == 放弃

//三维动规，时空都是On
func maxProfit(prices []int) int {
    pLen := len(prices)
    if pLen == 0{
        return 0
    }
    result := 0
    profit := make([][3][2]int, pLen)
    profit[0][0][0], profit[0][0][1] = 0, -prices[0]
    profit[0][1][0], profit[0][1][1] = 0, -prices[0]
    profit[0][2][0], profit[0][2][1] = 0, -prices[0]
    for i:=1; i<pLen; i++{
        profit[i][0][0] = profit[i-1][0][0]
        profit[i][0][1] = max(profit[i-1][0][1], profit[i-1][0][0] - prices[i])
        profit[i][1][0] = max(profit[i-1][1][0], profit[i-1][0][1] + prices[i])
        profit[i][1][1] = max(profit[i-1][1][1], profit[i-1][1][0] - prices[i])
        profit[i][2][0] = max(profit[i-1][2][0], profit[i-1][1][1] + prices[i])
    }
    result = max(profit[pLen-1][0][0], max(profit[pLen-1][1][0], profit[pLen-1][2][0]))
    return result
}
func max(m, n int)int{
    if m>n{
        return m
    }
    return n
}

//滚动数组 空间优化版 时间On,空间O1
func maxProfit(prices []int) int {
    //首先确定操作过程中的所有状态：
    //1.从来没有操作过       2.只买过一次
    //3.买过一次并且卖过一次  4.买卖过一次且又买了一次
    //5.买卖过两次

    buy1 := -prices[0] //第一天买的收益是 -1*第一天价格
    sell1 := 0   //第一天买了又卖了
    buy2 := -prices[0]
    sell2 := 0

    max := func(a, b int)int {
        if(a>b){return a}
        return b
    }

    //开始dp:
    for i:=0; i<len(prices); i++ {
        buy1 = max(buy1, -prices[i]) //第i天，要么从来没有买过并且决定今天买，要么今天不买
        sell1 = max(sell1, buy1+prices[i]) //第i天，要么只买过一次并且今天卖掉，要么今天不卖
        buy2 = max(buy2, sell1-prices[i])  //第i天，要么执行第二次买入，要么今天不买
        sell2 = max(sell2, buy2+prices[i]) //第i天，要么执行第二次卖出，要么今天不卖
    }

    return sell2
}