[LeetCode] 309. Best Time to Buy

原题

思路：
状态转移
出售股票的状态，最大利润有两种可能。
一，和昨天一样不动；二，昨天持有的股票今天卖掉。

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];
  }
};