动态规划

dp数组的含义这些跟121都一样，不同的是递推公式。
因为可以多次买卖

1. 所以当天持有股票的利润可以是
   1. ==前一天持有的利润，不操作
   2. 前一天不持有的利润-当天买入的价格

2. 当天不持有股票的利润

   1. ==前一天不持有的利润，不操作
   2. 前一天持有的利润+当天卖出的价格 ```javascript var maxProfit = function(prices) { let dp =new Array(prices).fill([0,0]) dp[0][0] =-prices[0] //持有股票的收益 dp[0][1] =0 //不持有股票的收益

   for(let i=1;i<prices.length;i++){

   dp[i] =[Math.max(dp[i-1][0],dp[i-1][1]-prices[i]),Math.max(dp[i-1][1],dp[i-1][0]+prices[i])]

   }

   return dp[prices.length-1][1]

};

- 时间复杂度：O(n)
- 空间复杂度：O(n)
<a name="QV3n8"></a>
## 滚动数组
```javascript
// 方法二：动态规划（滚动数组）
const maxProfit = (prices) => {
    // 滚动数组
    // have: 第i天持有股票最大收益; notHave: 第i天不持有股票最大收益
    let n = prices.length,
        have = -prices[0],
        notHave = 0;
    for (let i = 1; i < n; i++) {
        have = Math.max(have, notHave - prices[i]);
        notHave = Math.max(notHave, have + prices[i]);
    }
    // 最终手里不持有股票才能保证收益最大化
    return notHave;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

  贪心

  只计算每天的正利润
  122.买卖股票的最佳时机II