题解 | #买卖股票的最好时机(二)#
买卖股票的最好时机(二)
https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9
//吸取教训，任何题目不要固定思维，常规解法也就是贪婪解法可以很容易解
//动态规划解法几乎都是将问题分解成当天是否持有该股票
//并且也没说该怎么引导往这个方向上想
//我觉得冷不丁要想到对我来说还是有难度
//然后我就写一下我的思考过程作为笔记
//首先设定主问题就是以第N天结尾序列的最大收益f(N)（这个是基础）
//最后一天可以确定是不会执行买入操作的。
//所以对最后一天只能选择不动或者卖出操作所以f(N) = max(g(N)(不操作的最大收益)，t(N)（卖出操作的最大收益）)
//当选择不操作，那么最大的就是以N-1天结尾的最大收益,g(N) = f(N-1)
//当选择卖出操作，那上一次操作一定是买入，有可能在1...N-1任意一天买入，我假设n天买入最大收益为b(n)
//b(n) = f(n-1)-prices[n]，第n天买入最大收益等于n-1天最大收益减当天价格
//我要求t(N)是卖出最大收益,则选择b(n)买入收益最大那一天，所以t(N) = max(b(1),b(2)...b(N-1))+prices[N]
//看似他因为b(n)可以由f（n-1）表示，意味着t(N)也可以用f(N-1)表示了，自然可以用动态规划了
//提一点，看似他t（N）每次都要求一个买入的最大值，每次都要判断N-1次
//但是max(b(1),b(2)...b(N-1)) = max(max(b(1),...b(N-2)),b(N-1))，也可以用动态规划，所以复杂度还是n
//越说越复杂···就当是我这个菜鸟最后的挣扎吧，就像看看自己想能不能想出来
func maxProfit(prices []int) int { // write code here max := 0 maxbuy := 0 - prices[0] for i := 1; i < len(prices); i++ { if maxbuy+prices[i] > max { max = maxbuy + prices[i] } if max-prices[i] > maxbuy { maxbuy = max - prices[i] } } return max
}
查看21道真题和解析