[!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) {
    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;
};