dp方程:
首先今天作为第n天收益有两种情况,有无股票,用hold来保存有股票的收益情况,unhold保存无股票的收益
- 今天有股票那么可能是昨天就有或者今天买入,今天买入则昨天没有抛出(否则为冰冻期) hold[i]= Math.max(hold[i-1], unhold[i-2]-prices[i])
- 今天没有股票那么可能是昨天就没有或者昨天抛出,昨天抛出则前天unhold[i] = Math.max(unhold[i-1], hold[i-2]+prices[i])
注意边界初始化
最终结果手中没有股票
var maxProfit = function(prices) {
let n = prices.length
if(n<2) {return 0}
let hold = [-prices[0], Math.max(-prices[1], -prices[0])]
let unhold = [0, Math.max(prices[1]-prices[0], 0)]
for(let i=2; i<n; i++) {
hold[i] = Math.max(hold[i - 1], unhold[i - 2] - prices[i]);
unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
}
return unhold[n-1]
};