摘要：雙指針法復雜度時間空間思路根據(jù)買賣股票的特性，我們必須先低價買，再高價賣，這個找最大收益的過程實際上是找到目前為之的最低價。我們可以利用這個之前計算的結果降低時間復雜度不過代價是額外空間，所以需要把到的最大收益存在數(shù)組中。

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

時間 O(N) 空間 O(1)

根據(jù)買賣股票的特性，我們必須先低價買，再高價賣，這個找最大收益的過程實際上是找到目前為之的最低價。在遍歷價格數(shù)組時，根據(jù)這個動態(tài)更新的最低價和當前的價格可以算出當前賣股票最大能賺多少錢。

public class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, res = 0;
        for(int i = 0 ; i < prices.length; i++){
            if(prices[i]res) res = prices[i] - min;
        }
        return res;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

時間 O(N) 空間 O(1)

既然能買賣任意次，那最大收益的方法就是盡可能多的低入高拋。只要明天比今天價格高，就應該今天買入明天再賣出。

public class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
        }
        return sum;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

時間 O(N) 空間 O(N)

最簡單的方法就是對每一個時間點，將其所有兩邊的數(shù)組都執(zhí)行一次Best Time to Buy and Sell Stock I的解法，但這會帶來O(N^2)的時間復雜度。實際上當計算prices[0]到prices[i]的最大收益時，我們已經計算過prices[0]到prices[i-1]的最大收益了，prices[0]到prices[i]的最大收益應該是當前賣出能獲得的最大收益和prices[0]到prices[i-1]的最大收益中，二者較大的那個。我們可以利用這個之前計算的結果降低時間復雜度（不過代價是額外空間），所以需要把prices[0]到prices[i]的最大收益存在left[i]數(shù)組中。具體解法和I是一樣的，也是維護一個前半段最小值。

分別得出以i點為分割點，左半段最大收益的數(shù)組left，和右半段最大收益的數(shù)組right后，我們就可以遍歷一遍這兩個數(shù)組，找出最大的left+right組合。實際上，該解法就是將I的解法雙向各執(zhí)行一遍并記錄結果。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        int leftMin = prices[0];
        int rightMax = prices[prices.length-1];
        int sum = 0;
        //計算左半段最大收益
        for(int i = 1 ; i < prices.length; i++){
            leftMin = Math.min(prices[i], leftMin);
            left[i] = Math.max(prices[i] - leftMin, left[i-1]);
        }
        //計算右半段最大收益
        for(int i = prices.length - 2 ; i >= 0; i--){
            rightMax = Math.max(prices[i], rightMax);
            right[i] = Math.max(rightMax - prices[i], right[i+1]);
        }
        //找出兩次交易最大收益組合
        for(int i = 0 ; i < prices.length; i++){
            if((left[i]+right[i])>sum) sum = left[i]+right[i];
        }
        return sum;
    }
}

時間 O(N) 空間 O(1)

其實我們并不需要知道每個時間點買賣第一第二筆股票收益的全部信息，我們只要知道前一個時間點買賣第一第二筆股票的最大收益信息，就可以直到當前最大的收益信息了，這樣可以為我們省去額外空間。這里我們遍歷prices數(shù)組的時候，維護四個變量:release2是在該價格點賣出第二筆股票后手里剩的錢，等于上一輪買入第二筆股票后手里剩的錢加上賣出當前股票價格的錢，或者上一輪賣出第二筆股票后手里剩的錢兩者中較大的。hold2是在該價格點買入第二筆股票后手里剩的錢，等于上一輪賣出第一筆股票后手里剩的錢減去買入當前股票價格的錢，或者上一輪買入第二筆股票后手里剩的錢兩者中較大的。release1是在該價格點賣出第一筆股票后手里剩的錢，等于上一輪買入第一筆股票后手里剩的錢加上賣出當前股票價格的錢，或者上一輪賣出第一筆股票后手里剩的錢兩者中較大的。hold1是在該價格點買入第一筆股票后手里剩的錢，等于初始資金減去買入當前股票價格的錢或者初始資金（不買）中較大的。這里計算順序按照release2 -> hold2 -> release1 -> hold1，因為賣是要后于買的，而第二次交易也是后于第一次交易的，通過這個順序我們能用這些變量自身來記錄上次的值。相當于release2的時間點要先于hold1四個點。

Prices      3    1    2    8    3    1    9    6
release2    0    0    1    7    7    7    1    1
hold2      -3   -1   -1   -1    4    6    1    1
release1    0    0    1    7    7    7    1    1
hold1      -3   -1   -1   -1   -1   -1    3    3

public class Solution {
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i = 0; i < prices.length; i++){
            //在該價格點賣出第二筆股票后手里剩的錢，等于上一輪買入第二筆股票后手里剩的錢加上賣出當前股票價格的錢，或者上一輪賣出第二筆股票后手里剩的錢兩者中較大的
            release2 = Math.max(release2, hold2 + prices[i]);
            //在該價格點買入第二筆股票后手里剩的錢，等于上一輪賣出第一筆股票后手里剩的錢減去買入當前股票價格的錢，或者上一輪買入第二筆股票后手里剩的錢兩者中較大的
            hold2 = Math.max(hold2, release1 - prices[i]);
            //在該價格點賣出第一筆股票后手里剩的錢，等于上一輪買入第一筆股票后手里剩的錢加上賣出當前股票價格的錢，或者上一輪賣出第一筆股票后手里剩的錢兩者中較大的
            release1 = Math.max(release1, hold1 + prices[i]);
            //在該價格點買入第一筆股票后手里剩的錢，等于初始資金減去買入當前股票價格的錢或者初始資金（不買）中較大的
            hold1 = Math.max(hold1, -prices[i]);
        }
        return release2;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

時間 O(Nk) 空間 O(Nk)

我們將第i天已經執(zhí)行j筆交易的最大收益作為全局變量global，將第i天正好完成第j筆交易的最大收益作為局部變量local。

對于global，也就是我們要知道第i天已經執(zhí)行j筆交易的最大收益，可以基于第i-1天已經執(zhí)行j筆交易的最大收益和第i天正好完成第j筆交易的最大收益，即globali = max(globali-1, locali)。

對于local，也就是我們要知道第i天正好完成第j筆交易的最大收益，可以基于第i-1天正好完成第j-1筆交易的最大收益加上當天交易的差值，還有第i-1天正好完成第j筆交易的最大收益加上當天交易的差值。要注意的是，第i-1天正好完成第j-1筆交易這種情況，當前交易的差值取0和實際昨天今天差價中較大的，因為我們還有一次自由交易的余地，所以如果虧的話完全可以當天買賣避免損失。但第i-1天正好完成第j筆交易這種情況來推導第i天正好完成第j筆交易時，相當于第i天已經要連著第i-1天交易，使得第i-1天正好完成的第j筆交易和第i天正好完成的第j筆交易是同一個交易。算式是：locali = max(locali-1+max(0, diff), locali-1+diff)

對于k > prices.length / 2的情況，我們可以用II的解法來節(jié)省空間。因為按照題意必須先買后賣，那么對于n天交易，能夠產生有效收益的交易次數(shù)是小于等于n/2的，只有不同天買賣才能產生差價。對于大于n/2的那部分交易，必定是當天買賣沒有任何收益的，無論交易多少次都是一樣的。所以如果k > prices.length / 2，就相當于無限次交易。

數(shù)組的第二維初始化長度是k+1，因為我們要預留完成0筆交易的收益，是0。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0) return 0;
        //用II的解法優(yōu)化k > prices.length / 2的情況
        if(k > prices.length / 2){
            int sum = 0;
            for(int i = 1; i < prices.length; i++){
                if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
            }
            return sum;
        }
        //初始化全局變量和局部變量
        int[][] global = new int[prices.length][k+1];
        int[][] local = new int[prices.length][k+1];
        for(int i = 1; i < prices.length; i++){
            int diff = prices[i] - prices[i-1];
            for(int j = 1; j < k + 1; j++){
                //更新局部變量
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(0, diff), local[i-1][j]+diff);
                //更新全局變量
                global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }
        return global[prices.length - 1][k];
    }
}

時間 O(N) 空間 O(k)

這個解法和III中滾動掃描法是一樣的，區(qū)別在于III我們用了固定的四個變量來記錄兩次交易，而IV中我們需要2k個變量來記錄k次交易。

數(shù)組長度要初始為k+1，這樣方便我們處理第一筆交易的情況。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        //用II的解法優(yōu)化k > prices.length / 2的情況
        if(k > prices.length / 2){
            int sum = 0;
            for(int i = 1; i < prices.length; i++){
                if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
            }
            return sum;
        }
        //初始化買賣股票后剩余金錢的數(shù)組
        int[] release = new int[k+1];
        int[] hold = new int[k+1];
        for(int i = 0; i < k+1; i++){
            hold[i]=Integer.MIN_VALUE;
        }
        for(int i = 0; i < prices.length; i++){
            for(int j = 1; j < k+1; j++){
                //賣出第j筆交易，所剩余的錢
                release[j] = Math.max(release[j], hold[j]+prices[i]);
                //買入第j筆交易，所剩余的錢
                hold[j] = Math.max(hold[j], release[j-1]-prices[i]);
            }
        }
        return release[k];
    }
}

Q：如果對于每個時間點，都可以買入1次，而對于每個時間點，都可以賣出之前持有的任意多個股票，該如何計算？
A：因為可以持續(xù)持有多個之前買的股票，我們可以一直買入并持有，直到第一個全局最高點時再一起賣出去。接著我們再一直買入，直到剩余價格中的全局最高點時賣出去，以此類推。這里提供兩個解題思路：

先遍歷一遍找出所有峰值，并將這些峰值和他們的坐標打包起來，扔進一個Heap。這樣再從頭遍歷一遍，先拿出堆頂，把直到堆頂坐標之前的差值都累加起來，過了這個堆頂?shù)淖鴺撕笤倏聪乱粋€有效堆頂（有效堆頂是指下標在當前下標之后的）。時間復雜度O(NlogN)。

先找出全局最高點，然后在整個數(shù)組之前加一個最大值元素，這樣就把這道題轉換成了積水問題。時間復雜度O(N)。

Q: 如果每次交易有手續(xù)費怎么辦？
A: 手續(xù)費實際上就是降低了賣價（或者等同于提高了買價），我們根據(jù)手續(xù)費相應調整利潤就行了。