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

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路

  1. 找到多段单调递增区间并累加差值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var maxProfit = function (prices) {
  prices.unshift(Number.MAX_VALUE)
  prices.push(Number.MIN_SAFE_INTEGER)
  let result = 0
  let minVal = prices[0]
  for (let i = 1; i < prices.length; ++i) {
    if (prices[i] > prices[i - 1]) {
      continue
    }
    result += Math.max(0, prices[i - 1] - minVal)
    minVal = prices[i]
  }
  return result
}

进一步简化思路，最大利润 = 每天与前一天正向价差的累加

1
2
3
4
5
6
7
8
9
10
11
var maxProfit = function (prices) {
  let result = 0
  let prevPrice = Number.MAX_VALUE
  for (const curPrice of prices) {
    if (curPrice > prevPrice) {
      result += curPrice - prevPrice
    }
    prevPrice = curPrice
  }
  return result
}