算法细节系列（13）：买卖股票_算法 当买得越多亏损越多

买卖股票

详细代码可以fork下Github上leetcode项目，不定期更新。

该系列的题目意思很简单，但要在规定的时间复杂度内完成算法颇有难度。它有趣的地方在于它的解决思路。如果上一篇文章是为了破除想当然，那么这篇文章一定可以用异想天开来总结，我们一定得拎出一些核心的想法来引导算法。

题目均摘自leetcode，分为以下五题（买卖股票系列）。

• 121 Best Time to Buy and Sell Stock
• 122 Best Time to Buy and Sell Stock II
• 123 Best Time to Buy and Sell Stock III
• 188 Best Time to Buy and Sell Stock IV
• 309 Best Time to Buy and Sell Stock with Cooldown

121. Best Time to Buy and Sell Stock

Problem:

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

看到这道题的一瞬间，心里飘忽忽，心想，还不简单么。找个历史最低点，再找个历史最高点，求出maxProfit，呵呵，刚准备敲代码发现，不对啊，历史最高点由历史最低点决定啊（历史最高一定出现在历史最低后头），那就意味着得遍历所有历史最低点，然后寻找后续的历史最高点来求得maxProfit，那么最差就得$O(n^2)$的时间复杂度。

显然这思路就不符合题目对时间的要求。

思路1

上述问题的解决方案是最低级且暴力的，但我们会发现一个模式，它的每一个历史最低点都会向后找【所有】历史最高点去比较（你也可以看作是跟每个向后的历史值去比较，只要维护一个maxProfit即可），所以它可以逆向思考，也就是说，遍历到当前点，我们可以向前去比较历史最低点，不断更新maxProfit，遍历结束总能找到正确值。

所以一份简单的$O(n)$代码就出来了，如下：

    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i =0;i<prices.length;i++){
            if (prices[i] < minprice){
                minprice = prices[i];
            }else if (prices[i]-minprice > maxprofit){
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

但需要明确一点，之所以可以这样做，无非两点，之前的信息我们可记录（维护一个最小的minPrice变量），其次遍历的后向性所带来的好处，由问题本身决定（股票一定是先买后卖）。

思路2

这是一种思路，带来了$O(n)$的解决方案。再来看一种解决方案，核心思想如下：
1. 卖的同时可以瞬间买进。（多个操作可以看成一个操作）
2. 没钱的情况下，可以看作向别人借钱（记忆）

继续看另一版本的代码：

    public int maxProfit(int[] prices) {

        int buy = Integer.MIN_VALUE;
        int sell = 0;

        for (int price : prices){
            buy = Math.max(buy, -price);
            sell = Math.max(sell, buy + price);
        }

        return sell;
    }
1
2
3
4
5
6
7
8
9
10
11
12

虽然代码形式和上一种不太一样，但它们本质上是一种形式，可以互相转换。但该代码的好处在于它更加亲民接地气。更符合人的认知，buy可以看作是借钱的过程，而max是为了搜索价格最低的买点，sell是维护了最大的利益，而且很重要的一点它是势能突破函数，高一点就向上顶一下，非常形象。buy和sell同时操作price，这是另外一个神奇的地方，因为核心思想提到，卖的同时可以买进，如果只存在一个元素，该操作返回的sell还是为0，可以看作无操作，符合边界条件。

思路3

哈哈，它还有另外一种解法，它的买卖同时更加形象。利用的是势能不断增加，突破max就更新max，当价格下降时，势能降低，但最低不超过0。（sum减到0就停止更新），所以代码如下：

public int maxProfit(int[] prices) {
        int sum = 0;
        int max = 0;

        for (int i = 1; i < prices.length;i++){
            sum = Math.max(0, sum += prices[i]-prices[i-1]);
            max = Math.max(max, sum);
        }

        return max;
    }
1
2
3
4
5
6
7
8
9
10
11

就从整个prices的价格走势来看，只要有上升的情况，我们就可以使用sum += prices[i]-prices[i-1]来不断累计（卖的瞬间可以立马买进，多个操作的组合可以看成一个操作）。而当价格走势下降时，处于亏损状态，sum不断减小，而不会取负值。（此处是不会影响max的）。所以维持一个sum很关键，简单总结下，它是个变态势能累积函数（不公平势能累积），上升趋势总能被更新，而下降趋势，下降到0时，不记录势能sum中。好处是把上升趋势的最低点拔高到0势能点，从而可以不断更新较大的max。

以上三种思路都能引向正确答案，是不是很神奇。

122. Best Time to Buy and Sell Stock II

Problem:

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

解释了这么多，看到这道题你心里应该有答案了，选择哪种思路呢？

核心思想：
1. 检测出上升趋势
2. 势能函数直接累加上升趋势（单调递增的多个买卖操作可合并）

所以代码如下：

    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length -1; i++){
            if (prices[i+1] > prices[i]) max += prices[i+1] - prices[i];
        }
        return max;
    }
1
2
3
4
5
6
7

123. Best Time to Buy and Sell Stock III

Problem:

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

该题目主要约束了交易次数，最多只能2次。显然，以上提到的一些思路是无法扩展到该问题上的。如思路1所提到的后向查找，它本质上认为后续的最高点都是一样的，所以无法求解。思路3，同样地，对多断交易无法区分，它只能处理两种情况，一段交易和“无数段”交易。

思路2的想法相当独特，buy被看作“借钱”，而sell则看作是当前的即得利益。借钱的思路让人映象深刻，因为有了借钱我们就能联想到原本的财富余额（本金），无非刚开始本金为0咯，这就说明上一轮的sell可以转换成下一轮的本金，状态就出来了。再来看看思路1和思路3，你会发现，它们很难表示既得利益和本金的状态转换。所以代码如下：

 public int maxProfit(int[] prices) {
        int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            buy1 = Math.max(buy1, 0-prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
1
2
3
4
5
6
7
8
9
10

非常巧妙，在$O(n)$内就把问题给解决了，你会问了该思路怎么才能想到，我只能说神人自知。

简单说明一下该代码为何是正确的。首先看

buy1 = Math.max(buy1, 0 - prices[i]);
1

如果把i当作不断变动的变量的话，你可以总结出max的作用，有下降趋势的prices[i]总是被更新，所以刚开始的buy1一定能被更新到第一个下降趋势的最低点，就不再更新了。这就好像让buy1找到了一个最合适的位置。好，此时再看。

sell1 = Math.max(sell1, buy1 + prices[i]);
1

同理，当有下降趋势时，该函数不做任何操作，因为在下降过程，buy1+prices[i] = 0，而上升时，由于buy1不再更新，此时sell1将不断更新，所以sell1记录的就是不断上升的第一段maxProfit。

那么，为什么直接把buy2 = Math.max(buy2,sell1-prices[i])加在sell1后面就好了呢？它记录的也是最低点，且刚开始那一段下降和buy1的值几乎一模一样，此时的sell1 = 0，所以buy1 = buy2。当第一段下降结束开始上升时，sell1开始不断增大，而buy1停止了更新，buy2 = buy1 + prices[i] - prices[i] = buy1，所以它也始终不动。而此时的sell2 = buy2 + prices[i] = buy1 + prices[i] = sell1，所以得出第一段的上升和下降，buy1 = buy2, sell1 = sell2。这也就表明了，如果最多只能交易一次时，返回sell2同样正确。

第二段的下降，buy1总是【寻找历史最低点】，所以暂且不去看它，重点关注buy2的变化，因为buy2 = Math.max(buy2, sell1-prices[i])，而我们知道一旦产生利益，sell1 > 0，且第二段的下降总是出现在sell1达到最大值的下一时刻，所以buy2的范围在(0,sell1]，且时刻更新。这也就是说，不管第二阶段中的buy1 or sell1如何变化，在sell1刚开始下降的那个时刻，buy2会找到那个时刻后的最低点，此时再上升时，sell2的更新则在原有sell1的基础上，不断突破最大值。

那么你会问了，buy1有没有可能再次更新，答案是肯定有可能的。但它的更新不会影响在第一个时刻求得的sell1对后续sell2的影响。那它是如何选择最大的两次交易呢?很明显，因为buy1还在时刻变化着，如果它同样再更新过程再次突破sell1的最高值，那么我们又选定了一个候选点，此时，又开始一轮sell2的更新，如果同样地也突破了sell2的峰值，那么就被更新成了新的两次交易，依此类推，直到数组遍历结束。

的确比较绕，中间还有一些细节没搞明白，如为何每次按照历史最低点生成的sell1去更新sell2能够得到全局最优解？不求甚解。

188. Best Time to Buy and Sell Stock IV

Problem:

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

这次从2次变成了k次，自己做一次就知道了，就按照上述的思路，两次购买变成多次购买即可，但不幸会TLE，在这里需要做一些预处理。代码如下：

public int maxProfit(int k, int[] prices) {

        if (k == 0) return 0;

        if (k >=  prices.length/2) {
        int maxPro = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1])
                maxPro += prices[i] - prices[i-1];
        }
        return maxPro;
    }

        int[] sell = new int[k];
        int[] buy = new int[k];
        Arrays.fill(buy, Integer.MIN_VALUE);

        for (int i = 0; i < prices.length;i++){
            buy[0] = Math.max(buy[0], -prices[i]);
            sell[0] = Math.max(sell[0], buy[0]+prices[i]);
            for (int j = 1; j < k; j++){
                buy[j] = Math.max(sell[j-1]-prices[i], buy[j]);
                sell[j] = Math.max(buy[j]+prices[i], sell[j]);
            }
        }
        return sell[k-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

注意下开头的k >= prices.length / 2的判断，prices最多有prices/2次交易，当k超过次数时，说明它没有选择交易的余地，直接计算所有可能的上升趋势即可。

309. Best Time to Buy and Sell Stock with Cooldown

Problem:

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) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

可以多笔交易，但中间至少有一次停顿（不能交易），题目意思很简单。写出状态方程即可。

buy[i]  = max(rest[i-1]-price, buy[i-1]) 
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
1
2
3

代码如下：

public int maxProfit(int[] prices) {

        int n = prices.length;

        int[] buy = new int[n+1];
        int[] sell = new int[n+1];
        int[] rest = new int[n+1];

        buy[0] = Integer.MIN_VALUE;
        sell[0] = rest[0] = 0;

        for (int i = 0; i < n; i++) {

            buy[i+1] = Math.max(rest[i] - prices[i], buy[i]);
            sell[i+1] = Math.max(buy[i] + prices[i], sell[i]);
            rest[i+1] = Math.max(sell[i], Math.max(rest[i], buy[i]));
        }

        return sell[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20