LeetCode——买卖股票的最佳时机（动态规划+更新极值）

var maxProfit = function (prices) {
    // 通过不断更新最大值和最小值的方法来求解
    let maxPriceDiff = 0;
    let minPrice = prices[0];
    for (let i = 1; i < prices.length; i++) {
        minPrice = Math.min(prices[i], minPrice);
        let tempMax = Math.max(prices[i] - minPrice);
        maxPriceDiff = Math.max(maxPriceDiff, tempMax);
    }
    return maxPriceDiff;
};
复制代码

var maxProfit = function (prices) {
    // 通过动态规划的方法
    const dp = new Array(prices.length).fill([0, 0]);
    // 设置动态规划的初始值
    // 第0天不持股的情况下，手上的现金数
    dp[0][0] = 0;
    // 第1天持股的情况下，手上的现金数是当日价格的负数
    dp[0][1] = -prices[0];
    // 从第二天开始进行遍历
    for (let i = 1; i < prices.length; i++) {
        // 第i天手上不持股的情况：前一天不持股，或者前一天持股但是今天卖掉了
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        // 第i天手上持股的情况：前一天不持股，今天买入，或者前一天持股今天没卖
        dp[i][1] = Math.max(- prices[i], dp[i - 1][1]);
    }
    // 最终返回的就是最后一天不持股手上的最大现金数
    return dp[prices.length - 1][0]
};
复制代码