[!info] related notes 动态规划 区间 DP 与状态机 DP 股票最大资产

买卖股票的最佳时机

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

状态

• dp[i][0]：第 i 天结束后不持股的最大收益
• dp[i][1]：第 i 天结束后持股的最大收益

转移

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i])

最多完成一次交易，也可不交易。持股状态的新买入只能来自尚未交易的零收益，不能用已卖出后的收益继续买。这里“收益”指累计现金净额，持股时不计未卖出股票的估值；它不同于 多股与初始现金约束下的最大资产。

JavaScript

var maxProfit = function(prices) {
    if (prices.length === 0) return 0;
    let hold = -prices[0];
    let empty = 0;

    for (let i = 1; i < prices.length; i++) {
        empty = Math.max(empty, hold + prices[i]);
        hold = Math.max(hold, -prices[i]);
    }

    return empty;
};