Cocolib

Appearance

On this page

买卖股票的最佳时机II ​

TIP

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第i天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路 ​

贪心 ​

其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

js
var maxProfit = function(prices) {
    let res = 0
    let fit = 0
    for(let i=1; i<prices.length; i++){
        fit =  prices[i]-prices[i-1]
        if(fit>0)
            res += fit
    }
    return res
};

动归 ​

dp数组的含义：

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
js
var maxProfit = function(prices) {
    let dp =  Array(prices.length).fill().map(() => Array(2).fill(0))
    dp[0][0] = -1*prices[0]
    dp[0][1] = 0
    for(let i=1;i<prices.length;i++){
        dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i])
        dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i])
    }
    return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]) 
};