leetcode | go | 第309题 | 买卖股票的最佳时机含冷冻期_leetcode 309 买卖股票的最佳时机含冷冻期 golang

买卖股票的最佳时机含冷冻期

go

解决思路

1. n 为数组长度，如果长度为 1，那么返回 0，buys[i] 为第 i 天买入的最大值，sells[i] 为第 i 天卖出的最大值
2. 边界条件，buys[0]、buys[1] 设为第 0 天和第 1 天买入的情况，sells[0] 和 sells[1] 设为第 0天买入卖出，第 0 天买入第 1 天卖出的情况，ans 设初值为 sells[1] 和 sells[0] 的最大值（这样 ans 最小也为 0，后面不用再和 0 比大小了）
3. 从 2 到 n-1 遍历，a、b 的初值为 0，buys[i-1]（因为卖出的情况最差为 0，买入可能为负，所以 buys[i-1] 为初值）。j 从 i-2 遍历到 0，a 取 a 和 sells[j] 的最大值，b 取 b 和 buys[j] 的最大值（刚好一次遍历过两个），buys[i]=max(buys[i-1],a-prices[i])，sells[i]=max(sells[i-1],b+prices[i])（i-1 表示维持 i-1 天的状态不动，另一个为在第 i 天买入、卖出的情况），ans 根据 sells[i] 进行更新
4. return ans
5. 时间不太好
6. 题解思路：（1）动态规划
7. 优化了一下代码，状态传递，i-1 表示维持 i-1 天的状态不变，那么状态实际上是传递到了 i 天，所以边界条件也进行状态传递，现在，buys[i] 表示到第 i 天手上持有一支股票的最大值，sells[i] 表示到第 i 天手上没有股票的最大值

相关问题

1. 如果只有两个元素，且 ans 设初值小于 0，那么 ans 得和 0 比较返回最大值
2. b 不应该设为初值 0，因为第一次买入肯定小于 0，和 0 比较肯定都小，那么设为 buys[i-1]
3. 虽然不知道为什么，但是把 buys 和 sells 的更新条件换为，buys[i-1] 和 sells[i-1] 而不是 i，就对了（i-1 的话，是保持 i-1 天的状态不动，不一定会 =0，如果设 i 那么就其实是和 0 比较）
4. buys[1] 初值不能用 buys[0] 比较，因为一起赋值，buys[0] 初始为 0

func maxProfit(prices []int) int {
    n:=len(prices)
    if n==1 {
        return 0
    }
    buys:=make([]int,n)
    sells:=make([]int,n)
    buys[0],buys[1]=-prices[0],max(-prices[0],-prices[1])
    sells[0],sells[1]=0,max(sells[0],-prices[0]+prices[1])
    ans:=sells[1]
    for i:=2;i<n;i++ {
        buys[i]=max(buys[i-1],sells[i-2]-prices[i])
        sells[i]=max(sells[i-1],buys[i-1]+prices[i])
        ans=max(ans,sells[i])
    }
    return ans
}
 
func max(a,b int) int { 
    if a>b {
        return a
    }
    return b
}
/*
func maxProfit(prices []int) int {
    n:=len(prices)
    if n==1 {
        return 0
    }
    buys:=make([]int,n)
    sells:=make([]int,n)
    buys[0],buys[1]=-prices[0],-prices[1]
    sells[0],sells[1]=0,-prices[0]+prices[1]
    ans:=max(sells[0],sells[1])
    for i:=2;i<n;i++ {
        a,b:=0,buys[i-1]
        for j:=i-2;j>=0;j-- {
            a=max(a,sells[j])
            b=max(b,buys[j])
        }
        buys[i]=max(buys[i-1],a-prices[i])
        sells[i]=max(sells[i-1],b+prices[i])
        ans=max(ans,sells[i])
    }
    return ans
}
func max(a,b int) int { 
    if a>b {
        return a
    }
    return b
}
*/