动态规划:
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
const n = prices.length // prices 长度,避免重复计算
if (n < 1) { // prices 长度为 0, 返回 0
return 0
}
let minPrices = new Array(n) // 用于存储 prices 每一天的最低价格
let maxProfit = new Array(n) // 用于存储每一天的最大收益
// 初始化
minPrices[0] = prices[0]
maxProfit[0] = 0
// 遍历数组
for (let i = 1; i < n; i++) {
// 计算第 i 天之前的最低价格等于,第 i 天与 i - 1 天,取更小的值
minPrices[i] = Math.min(minPrices[i - 1], prices[i])
// 计算第 i 天的最大收益, Max(前一天的最大收益, 今天卖出的价格 - 第(i - 1)天最低的价格),取更大的值
maxProfit[i] = Math.max(maxProfit[i - 1], prices[i] - minPrices[i - 1])
}
return maxProfit[n - 1]
};