[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown(medium)

原题

思路：

状态转移

出售股票的状态，最大利润有两种可能。

一，和昨天一样不动；二，昨天持有的股票今天卖掉。

sell[i] = max(sell[i-1],buy[i-1] + prices[i]);

购买股票的状态，最大利润有两种可能。

一，和昨天一样不动；二，两天前出售，今天购买。

bdp[i] = Math.max(bdp[i-1],sell[i-2] - prices[i]);

 class Solution

{

public:

  int maxProfit(vector<int> &prices)

  {

    if (prices.size() == 0)

      return 0;

    int len = prices.size();

    vector<int> buy(len + 1, 0), sell(len + 1, 0);

    buy[1] = -prices[0];

    for (int i = 2; i <= len; i++)

    {

      buy[i] = max(buy[i - 1], sell[i - 2] - prices[i - 1]);

      sell[i] = max(sell[i - 1], buy[i - 1] + prices[i - 1]);

    }

    return sell[len];

  }

};

巴特西

[leetcode] 309. Best Time to Buy and Sell Stock with Cooldown(medium)

原题

最新文章

热门文章