SOURCE

// 思路
// 本题求累计利润最大值 那依据的就是之前的利润值
// 注意 当天未持股时利润 = 前一天持股时手头金额 + 今天卖出股票的钱 - 手续费
// 当天持股时剩余利润 = 前一天未持股时手头金额 - 今天股价
// 最后取两者中最大值

function fn(prices, fee) {
    // 创建数组哈希表 记录每天 持股时利润hold 和 未持股时利润cash
    let map = new Array(prices.length).fill({ cash: 0, hold: 0 })
    // 先初始化第一天 第一天默认买入股票
    // 所以cash为0 而因为买入股票 hold为负
    map[0].hold = map[0].cash - prices[0]
    // 从第二天开始观察是否卖出
    for (let i = 1; i < prices.length; i++) {
        // 第i天cash 对比 前一天cash 和 假如今天卖出股票累计利润cash
        map[i].cash = Math.max(map[i - 1].cash, map[i - 1].hold + prices[i] - fee)
        // 第i天hold 对比 前一天hold 和 假如今天买入股票剩余利润
        map[i].hold = Math.max(map[i - 1].hold, map[i - 1].cash - prices[i])
    }
    // 对比 持股时累计利润 和 未持股时累计利润
    return Math.max(map[prices.length - 1].cash, map[prices.length - 1].hold)
}

// 验证
const prices = [1, 3, 2, 8, 4, 9]
const fee = 2
console.log(fn(prices, fee)) // 8