淘先锋技术网

首页 1 2 3 4 5 6 7

本文整理了leetcode上关于股票买卖最大利润系列问题的通用解法。这列问题通常是用动态规划来解。
首先来看通用的问题:

1. 给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
这是leetcode上的第188
解决这类问题的思路是创建两个数组,buy和sell,对于每天的股票价格,buy[j]代表第j次买入时的最大利润,sell[j]代表第j次卖出时的最大利润。

class Solution {
    //当k小于总天数时
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
        Arrays.fill(sell, 0);

        for (int i = 0; i < n; i ++) {
            for (int j = 1; j <= k; j ++) {
                buy[j] = Math.max(buy[j], sell[j-1] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k];
    }
}

2. 如果遇到特例,比如k=2,那么就把上面的方法中的k改为2就可以了。如果只能交易一次,也就是说k=1, 上面的解答方法中的数组就可以用变量来表示了。

class Solution {
   public int maxProfit(int k, int[] prices) {
       int n = prices.length;
       int buy = Integer.MIN_VALUE;
       int sell = 0;
       
       for (int i = 0; i < n; i ++) {
          /**
          可以假设上例中的k=1,那么buy和sell都是拥有两个元素的数组,
          则上例中的更新两个数组可以表示为:
          buy[1] = Math.max(buy[1], sell[0] - prices[i])
          sell[1] = Math.max(sell[1], buy[1] + prices[i])
          所以这个for循环一直在更新buy[1]和sell[1]的值,
          把sell[0] = 0代入上式,即可得到下式。
          **/
           buy = Math.max(buy,  - prices[i]);
           sell = Math.max(sell, buy + prices[i]);
       }
       return sell;
   }
}

3. 如果交易次数不限呢?你可以令k=n,但这样的结果可能会超时,因为有两个for循环,复杂度是o(n*n).
具体题目参见leetocde第122题.
可以简化成:

class Solution {
    public int maxProfit(int[] prices) {
       int n = prices.length;
        int buy = Integer.MIN_VALUE;
        int sell = 0;

        for (int i = 0; i < n; i ++) {
            /**
            因为可以交易无限次,那么这次买入时收益的最大值会与上一次卖出时收益的最大值有关。
            而如果只能交易一次,那么这一次买入的时候,上一次一定没有卖出。
            **/
            buy = Math.max(buy, sell - prices[i]);
            sell = Math.max(sell, buy + prices[i]);
        }
        return sell;
    }
}

4. 如果每次交易的时候都需要手续费。leetcode第714
因为也可以无限次交易,所以答案和第3题差不多,只是多了个手续费的问题。我们可以这样考虑,最后股票一定会卖出,这样才能得到最大的利润,而没交易一次,只算一次手续费,所以可以把手续费的扣除动作放在sell中

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int buy = Integer.MIN_VALUE;
        int sell = 0;

        for (int i = 0; i < n; i ++) {
            buy = Math.max(buy, sell - prices[i]);
            sell = Math.max(sell, buy + prices[i] - fee);
        }
        return sell;
    }
}

5.最后比较难的是包含冷冻期的题目。leetcode第309题。这个题目不一样的地方在于卖出之后,不能立即买入,需要经过至少一天的冷冻期。
所以这个题目包含四种状态:
s2: 最后一个操作是卖出股票后的冷冻期的最大利润
buy:最后一个操作是买入股票后的最大利润
s1:最后一个操作是卖出股票后的冷冻期的最大利润
sell: 最后一个操作是卖出股票后的最大利润
在这里插入图片描述

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy = Integer.MIN_VALUE, s1 = Integer.MIN_VALUE;
        int sell = 0, s2 = 0;
        for (int i = 0; i < n; i++) {
            s1 = Math.max(s1, buy);
            buy = s2 - prices[i];
            s2 = Math.max(s2, sell);
            sell = Math.max(buy + prices[i], s1 + prices[i]);
        }
        return Math.max(s2, sell);
    }
}

s1[i]的状态可以由buy[i-1]变化而来,也可以由s1[i-1]变化而来,取两者的较大值。如果想要压缩空间,那么s1的更新要在buy之前,否则buy更新后就变成今天的值了,而不是前一天的值了
buy[i]的状态只能由冷冻期(s2[i-1])通过买入股票而来
s2[i]可以由s2[i-1]而来,也可以是sell[i-1]而来。
sell[i]可以由buy[i-1]卖出股票而来,也可以由s1[i-1]卖出股票而来。

注意:以上方法都是要先更新buy再更新sell。可以这么想象:可以在第i天先买入股票,然后再卖出,但不能在第i天先卖出然后再买入股票。所以更新buy的时候一定要用到sell未更新的值,但更新sell的时候,可以用buy更新后的值。