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

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

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).

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

既然能買(mǎi)賣(mài)任意次，那最大收益的方法就是盡可能多的低入高拋。只要明天比今天價(jià)格高，就應(yīng)該今天買(mǎi)入明天再賣(mài)出。

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).

時(shí)間 O(N) 空間 O(N)

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

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

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;
        //計(jì)算左半段最大收益
        for(int i = 1 ; i < prices.length; i++){
            leftMin = Math.min(prices[i], leftMin);
            left[i] = Math.max(prices[i] - leftMin, left[i-1]);
        }
        //計(jì)算右半段最大收益
        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;
    }
}

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

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

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++){
            //在該價(jià)格點(diǎn)賣(mài)出第二筆股票后手里剩的錢(qián)，等于上一輪買(mǎi)入第二筆股票后手里剩的錢(qián)加上賣(mài)出當(dāng)前股票價(jià)格的錢(qián)，或者上一輪賣(mài)出第二筆股票后手里剩的錢(qián)兩者中較大的
            release2 = Math.max(release2, hold2 + prices[i]);
            //在該價(jià)格點(diǎn)買(mǎi)入第二筆股票后手里剩的錢(qián)，等于上一輪賣(mài)出第一筆股票后手里剩的錢(qián)減去買(mǎi)入當(dāng)前股票價(jià)格的錢(qián)，或者上一輪買(mǎi)入第二筆股票后手里剩的錢(qián)兩者中較大的
            hold2 = Math.max(hold2, release1 - prices[i]);
            //在該價(jià)格點(diǎn)賣(mài)出第一筆股票后手里剩的錢(qián)，等于上一輪買(mǎi)入第一筆股票后手里剩的錢(qián)加上賣(mài)出當(dāng)前股票價(jià)格的錢(qián)，或者上一輪賣(mài)出第一筆股票后手里剩的錢(qián)兩者中較大的
            release1 = Math.max(release1, hold1 + prices[i]);
            //在該價(jià)格點(diǎn)買(mǎi)入第一筆股票后手里剩的錢(qián)，等于初始資金減去買(mǎi)入當(dāng)前股票價(jià)格的錢(qián)或者初始資金（不買(mǎ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).

時(shí)間 O(Nk) 空間 O(Nk)

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

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

對(duì)于local，也就是我們要知道第i天正好完成第j筆交易的最大收益，可以基于第i-1天正好完成第j-1筆交易的最大收益加上當(dāng)天交易的差值，還有第i-1天正好完成第j筆交易的最大收益加上當(dāng)天交易的差值。要注意的是，第i-1天正好完成第j-1筆交易這種情況，當(dāng)前交易的差值取0和實(shí)際昨天今天差價(jià)中較大的，因?yàn)槲覀冞€有一次自由交易的余地，所以如果虧的話(huà)完全可以當(dāng)天買(mǎi)賣(mài)避免損失。但第i-1天正好完成第j筆交易這種情況來(lái)推導(dǎo)第i天正好完成第j筆交易時(shí)，相當(dāng)于第i天已經(jīng)要連著第i-1天交易，使得第i-1天正好完成的第j筆交易和第i天正好完成的第j筆交易是同一個(gè)交易。算式是：locali = max(locali-1+max(0, diff), locali-1+diff)

對(duì)于k > prices.length / 2的情況，我們可以用II的解法來(lái)節(jié)省空間。因?yàn)榘凑疹}意必須先買(mǎi)后賣(mài)，那么對(duì)于n天交易，能夠產(chǎn)生有效收益的交易次數(shù)是小于等于n/2的，只有不同天買(mǎi)賣(mài)才能產(chǎn)生差價(jià)。對(duì)于大于n/2的那部分交易，必定是當(dāng)天買(mǎi)賣(mài)沒(méi)有任何收益的，無(wú)論交易多少次都是一樣的。所以如果k > prices.length / 2，就相當(dāng)于無(wú)限次交易。

數(shù)組的第二維初始化長(zhǎng)度是k+1，因?yàn)槲覀円A(yù)留完成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];
    }
}

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

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

數(shù)組長(zhǎng)度要初始為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;
        }
        //初始化買(mǎi)賣(mài)股票后剩余金錢(qián)的數(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++){
                //賣(mài)出第j筆交易，所剩余的錢(qián)
                release[j] = Math.max(release[j], hold[j]+prices[i]);
                //買(mǎi)入第j筆交易，所剩余的錢(qián)
                hold[j] = Math.max(hold[j], release[j-1]-prices[i]);
            }
        }
        return release[k];
    }
}

Q：如果對(duì)于每個(gè)時(shí)間點(diǎn)，都可以買(mǎi)入1次，而對(duì)于每個(gè)時(shí)間點(diǎn)，都可以賣(mài)出之前持有的任意多個(gè)股票，該如何計(jì)算？
A：因?yàn)榭梢猿掷m(xù)持有多個(gè)之前買(mǎi)的股票，我們可以一直買(mǎi)入并持有，直到第一個(gè)全局最高點(diǎn)時(shí)再一起賣(mài)出去。接著我們?cè)僖恢辟I(mǎi)入，直到剩余價(jià)格中的全局最高點(diǎn)時(shí)賣(mài)出去，以此類(lèi)推。這里提供兩個(gè)解題思路：

先遍歷一遍找出所有峰值，并將這些峰值和他們的坐標(biāo)打包起來(lái)，扔進(jìn)一個(gè)Heap。這樣再?gòu)念^遍歷一遍，先拿出堆頂，把直到堆頂坐標(biāo)之前的差值都累加起來(lái)，過(guò)了這個(gè)堆頂?shù)淖鴺?biāo)后再看下一個(gè)有效堆頂（有效堆頂是指下標(biāo)在當(dāng)前下標(biāo)之后的）。時(shí)間復(fù)雜度O(NlogN)。

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

Q: 如果每次交易有手續(xù)費(fèi)怎么辦？
A: 手續(xù)費(fèi)實(shí)際上就是降低了賣(mài)價(jià)（或者等同于提高了買(mǎi)價(jià)），我們根據(jù)手續(xù)費(fèi)相應(yīng)調(diào)整利潤(rùn)就行了。