买卖股票最佳时机 II

[!abstract] 问题 可以交易无限次，但每天只能持有一股。

示例

输入: prices = [7,1,5,3,6,4]
输出: 7
解释:
- 第2天买入(1)，第3天卖出(5)，利润=4
- 第4天买入(3)，第5天卖出(6)，利润=3
- 总利润=7

解法

方法1: 贪心

function maxProfit(prices: number[]): number {
  let profit = 0;

  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }

  return profit;
}

方法2: DP

function maxProfitDP(prices: number[]): number {
  let dp0 = 0;           // 不持有
  let dp1 = -Infinity;   // 持有

  for (const price of prices) {
    const newDp0 = Math.max(dp0, dp1 + price);  // 卖出
    const newDp1 = Math.max(dp1, dp0 - price);  // 买入
    dp0 = newDp0;
    dp1 = newDp1;
  }

  return dp0;
}

核心思想

只要明天比今天高，今天买明天卖
等价于累加所有上涨区间

复杂度

方法	时间	空间
贪心	O(n)	O(1)
DP	O(n)	O(1)

---

参见: **股票问题** | **买卖股票最佳时机** | **买卖股票最佳时机III**