题目

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

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示：

• 1 <= prices.length <= 5000

• 0 <= prices[i] <= 1000

  解题方法

  动态规划

  设定动态数组dp01表示当前持有股票时的最大收益，dp10, dp11分别表示前一天和今天不持有股票时的最大收益，由于由一天的冷却器，所以需要根据一天前不持有的状态推导今天持有股票的状态，具体递推公式如下：
  
  时间复杂度O(n)，空间复杂度O(1)
  C++代码：

  class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;
        int dp01 = -prices[0];
        int dp10 = 0, dp11 = 0;
        for(int i=1; i<prices.size(); i++) {
            int tmp0 = dp01;
            dp01 = max(dp01, dp10-prices[i]);
            dp10 = dp11;
            dp11 = max(dp11, tmp0+prices[i]);
        }
        return dp11;
    }
  };