題目描述

給定一個數(shù)組 prices ，其中 prices[i] 表示股票第 i 天的價格。
在每一天，你可能會決定購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以購買它，然后在 同一天 出售。
返回 你能獲得的 最大 利潤 。

示例 1:

輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

輸入: prices = [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:

輸入: prices = [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

題解

解題思路1 - 計算所有正增長

由于股票的購買沒有限制,那么把能賺錢的交易都累加上就是最大利潤了
每天的盈利都獲得，每天的虧損都規(guī)避。
所以最大收益就是每天比前一天的正差價總和

+ (int)maxProfit1:(NSArray *)prices {
    int ans = 0;
    for (int i=1; i<prices.count; i++) {
        if ([prices[i] intValue]>[prices[i-1] intValue]) {
            ans += [prices[i] intValue] - [prices[i-1] intValue];
        }
    }
    return ans;
}

    static public func maxProfit1(_ prices: [Int]) -> Int {
        var ans = 0;
        for i in 1..<prices.count {
            if prices[i] > prices[i-1] {
                ans += prices[i] - prices[i-1]
            }
        }
        return ans;
    }

解題思路 2 - 貪心算法

由于股票的購買沒有限制，因此整個問題等價于尋找x個不相交的區(qū)間(li,ri],使得x個區(qū)間的a[ri]-a[li]的和值最大。
x
∑ a[ri] - a[li]
i=1
其中l(wèi)i表示第li天買入的值，ri表示第ri天賣出

其中區(qū)間（li,ri]貢獻的價值為a[ri]-a[li],其實等價于(li,li+1],(li+1,li+2],...(ri-1,ri]這若干個區(qū)間長度為1的區(qū)間的價值和,即a[ri]-a[li] = (a[ri]-a[ri-1]) + (a[ri-1]-a[ri-2]) + ... + (a[li+1]-a[li]),因此問題可以簡化為找x個長度為1的區(qū)間(li,li+1],使得x個區(qū)間的a[li+1]-a[li]的和值最大

x
∑ a[li+1] - a[li] 值最大
I=1

貪心的角度考慮我們每次選擇貢獻大于0的區(qū)間即能使得答案最大化，因此最后答案為
n-1
∑ max{0,a[i] - a[i-1]}
i=1

+ (int)maxProfit2:(NSArray *)prices {
    int ans = 0;
    for (int i=1; i<prices.count; i++) {
        ans += MAX(0, [prices[i] intValue] - [prices[i-1] intValue]);
    }
    return ans;
}

    static public func maxProfit2(_ prices: [Int]) -> Int {
        var ans = 0;
        for i in 1..<prices.count {
            ans += max(0, prices[i] - prices[i-1])
        }
        return ans;
    }

解題思路 3 - 動態(tài)規(guī)劃

考慮到「不能同時參與多筆交易」，因此每天交易結(jié)束后只可能存在手里有一支股票或者沒有股票的狀態(tài)

定義狀態(tài)dp[i][0]表示第i天交易后手里沒有股票的最大利潤，dp[i][1]表示第i天交易完后手里持有一只股票的最大利潤，i從0開始

dp[i][0]的轉(zhuǎn)移方程，這一天交易完后手里沒有股票，那么可能的轉(zhuǎn)移狀態(tài)為前一天已經(jīng)沒有股票，即dp[i-1][0],或者前一天結(jié)束時持有股票，即dp[i-1][1],這時候我們要將其賣出并獲到當(dāng)天的收益prices[i],即dp[i-1][1]+prices[i],因此為了收益最大化，我們列出如下的轉(zhuǎn)移方程：
dp[i][0] = max{dp[i-1][0],dp[i-1][1]+prices[I]}

dp[i][1]的轉(zhuǎn)移方程，這一天交易完后手里還有股票，那么可能的轉(zhuǎn)移狀態(tài)為前一天手里就有股票，即dp[i-1][1],或者前一天結(jié)束時沒有股票，即dp[i-1][0],這時候我們需要買進股票并減少收益prices[i],即dp[i-1][0]-prices[i],因此為了收益最大化，我們列出如下的轉(zhuǎn)移方程：
dp[i][1] = max{dp[i-1][1],dp[i-1][0]-prices[I]}

對于初始狀態(tài)，根據(jù)狀態(tài)定義我們可以知道第0天交易結(jié)束的時候dp[0][0] = 0,dp[0][1] = -prices[0]

因此，我們只要從前往后依次計算狀態(tài)即可。由于全部交易結(jié)束后，持有股票的收益一定低于不持有股票的收益,因而dp[n-1][0] 一定大于dp[n-1][1]的，因而最后的答案是dp[n-1][0]

+ (int)maxProfit3:(NSArray *)prices {
    int n = (int)prices.count;
    int dp[n][2];
    dp[0][0] = 0;
    dp[0][1] = -[prices[0] intValue];
    for (int i=1; i<n; i++) {
        dp[i][0] = MAX(dp[i-1][0], dp[i-1][1]+[prices[i] intValue]);
        dp[i][1] = MAX(dp[i-1][1], dp[i-1][0]-[prices[i] intValue]);
    }
    return dp[n-1][0];
}

    static public func maxProfit3(_ prices: [Int]) -> Int {
        let n = prices.count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: 2), count: n)
        
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        
        for i in 1..<n {
            dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
        }
        return dp[n-1][0]
    }

優(yōu)化上述動態(tài)規(guī)劃

注意到上面的狀態(tài)轉(zhuǎn)移方程中，每一天的狀態(tài)只與前一天的狀態(tài)有關(guān)，而與更早的狀態(tài)都無關(guān)，因此我們不必存儲這些無關(guān)的狀態(tài)，只需要將dp[i?1][0] 和dp[i?1][1] 存放在兩個變量中，通過它們計算出dp[i][0] 和dp[i][1] 并存回對應(yīng)的變量，以便于第i+1 天的狀態(tài)轉(zhuǎn)移即可。

+ (int)maxProfit4:(NSArray *)prices {
    int n = (int)prices.count;
    int dp0 = 0;
    int dp1 = -[prices[0] intValue];
    for (int i=1; i<n; i++) {
        int newDp0 = MAX(dp0, dp1+[prices[i] intValue]);
        int newDp1 = MAX(dp1, dp0-[prices[i] intValue]);
        dp0 = newDp0;
        dp1 = newDp1;
    }
    return dp0;
}

    static public func maxProfit4(_ prices: [Int]) -> Int {
        let n = prices.count
        var dp0:Int = 0
        var dp1:Int = -prices[0]
        
        for i in 1..<n {
            let newDp0:Int = max(dp0, dp1+prices[i])
            let newDp1:Int = max(dp0-prices[i],dp1)
            dp0 = newDp0
            dp1 = newDp1
        }
        return dp0
    }

參考 https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/