给你一个整数数组 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
}