LeetCode——買賣股票的最佳時機（動态規劃+更新極值）

題目描述

思路一：更新最大值和最小值

• 首先，假設第一個元素是價格最小的值minPrice。
• 定義一個價格最大差maxPriceDiff，并設定值為0。
• 從數組的第二個元素開始更新價格最大差和最小值。
• 最小值是在第i個元素和前面的最小值minPrice之間進行比較。
• 最大價格差則是在前面的最大價格差和（第i天的股票價值-前面的最小值)之間進行比較。
• 最後傳回最大價格差。

AC代碼

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;
};
複制代碼      

思路二：動态規劃

詳細的思路請看代碼中的注釋。 需要我們注意的是：本題中隻能進行一次交易，例如如果你今天買入那麼你手上的現金就是-prices[i]。

dp數組以及下标的含義

• dp[i][0]：表示第i天，手裡不持有股票的現金數
• dp[i][1]：表示第i天，手裡持有股票的現金數

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]
};
複制代碼      

題目反思

• 學會使用動态規劃來求解買賣股票的問題
• 學會通過不斷更新最大值和最小值的方法來求解這個問題。
• 動态規劃最重要的是了解dp數組及其下标的含義并準确列出動态規劃的方程。