LeetCode_133_BestTimeToBuyAndSellStockIII

LeetCode
发布日期:   2022-06-24
更新日期:   2022-07-09
文章字数:   1.9k
阅读时长:   8 分
阅读次数:  

1. question: 买卖股票的最佳时机III（困难）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

示例 1:

1
2
3
4
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

1
2
3
4
5
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

1
2
输入：prices = [1]
输出：0

提示：

1
2
1 <= prices.length <= 105
0 <= prices[i] <= 105

2. answers

这道题既不是交易一次，也不是交易多次，而是最多交易两次。交易两次，一定是将数组分成了两部分【肯定不会相交的】。分别在两部分计算各自的一次交易最大值。同时，这两部分组成了数组的全部值，因将数组分为【0，x】和【x，n】即可。x的取值有1到n-1，即有n-1对两次交易，此时比较n-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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution_0133 {

    // 计算给定区间内的一次交易最大值。
    public int maxP(int[] prices, int start, int end) {

        if(start >= prices.length) return 0;

        // 初始化
        int maxValue = 0;
        int low = start;

        for (int i = start; i <= end; i++) {

            if(prices[i] < prices[low]) low = i;

            maxValue = Math.max(maxValue, prices[i] - prices[low]);
        }

        return maxValue;

    }

    public int maxProfit(int[] prices) {

        if(prices.length <= 1) return 0;

        int[] finalRes = new int[prices.length - 1];

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

        int maxValue = 0;
        for(int val: finalRes)
            maxValue = Math.max(maxValue, val);

        return maxValue;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] prices = {3,3,5,0,0,3,1,4};
//        int[] prices = {1,2,3,4,5};
//        int[] prices = {7,6,4,3,1};
//        int[] prices = {1};
        int[] prices = {1,3};

        Solution_0133 s = new Solution_0133();

        System.out.println(s.maxProfit(prices));
    }
}

显然，这是暴力法，超时了。存在很多重复计算，比如在计算[1,3]的时候，会用到[1,2]的结果，即对[1,2]进行了重复计算。此时，可按照一次交易的方法，逐个保存较小范围的值，后续较大范围直接取即可。

那么对于[x,n]、[x-1,n]等同理，先计算[n-1, n]的最优解，然后[n-2, n]的最优解直接使用前面的即可。代码如下所示：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Solution_0133_02 {

    public int maxProfit(int[] prices) {

        if(prices.length <= 1) return 0;

        // 保存[0,x]的最大值
        int[] dpFirst = new int[prices.length];

        // 保存[y,n]的最大值
        int[] dpSecond = new int[prices.length];

        // 动态规划 [0,x]
        dpFirst[0] = 0;
        int low = 0;
        for (int i = 1; i < prices.length; i++) {

            if(prices[i] < prices[low]) low = i;
            dpFirst[i] = Math.max(dpFirst[i-1], prices[i] - prices[low]);
        }

        // 动态规划[x,n]
        // 注意，因为需要从后向前遍历，即找的不再是最小值，应该是最大值。
        dpSecond[prices.length - 1] = 0;
        int high = prices.length - 1;
        for (int i = prices.length - 2; i >= 0; i--) {

            if(prices[i] > prices[high]) high = i;
            dpSecond[i] = Math.max(dpSecond[i+1], prices[high] - prices[i]);
        }

        // 比较n-1次搭配。
        int[] result = new int[prices.length];
        result[0] = 0;
        // 为了方便，此时的i表示两次交易断开的位置，即和dpFirst、dpSecond是等价的下标
        for (int i = 1; i < result.length; i++) {
            result[i] = Math.max(0, dpFirst[i]) + Math.max(0, dpSecond[i]);
        }

        // 取n-1次最大值
        int maxValue = 0;
        for(int value: result)
            maxValue = Math.max(maxValue, value);

        return maxValue;
    }

    public static void main(String[] args) {
        System.out.println();

        int[] prices = {3,3,5,0,0,3,1,4};
//        int[] prices = {1,2,3,4,5};
//        int[] prices = {7,6,4,3,1};
//        int[] prices = {1};
//        int[] prices = {1,3};

        Solution_0133_02 s = new Solution_0133_02();

        System.out.println(s.maxProfit(prices));
    }
}

上面的做法不具有代表性。比如如果规定最多交易n次，显然上面的方法就不能推广了。利用动态规划，二维数组，其实可以看到，虽然本题要求最多两次，本质上和只有一次交易以及无限次交易是类似的。

因为一天交易，可限制本天买入时的取值由前面状态得到，无限次就无需限制。那么两次的话，就不容易限制了。此时，可将每天的状态继续拆分。第一次持有、第一次不持有、第二次持有、第二次不持有。

显然第一次持有、不持有的状态和一次交易时是一样的。第二次持有可由如下状态得到：

  1. 前一天第二次持有
  2. 第一天第一次不持有，本天买入

二者取最大值即可。第二次不持有可由如下状态得到：

  1. 前一天第二次不持有
  2. 前一天第二次持有，本天卖出

二者取最大值即可。还有一点，就是第0天初始化，dp[0][0]显然就是-prices[0]，那么第二次持有呢，此时就相当于第-1天是没有利润的，第二次持有依然是-prices[0]。

代码如下所示：

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
28
29
30
31
32
33
34
35
36
public class Solution_0133_04 {

    public int maxProfit(int[] prices) {

        if(prices.length <= 1) return 0;

        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;

        for (int i = 1; i < prices.length; i++) {

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

            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]);
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
        }

        return dp[dp.length - 1][3];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0133_04 s = new Solution_0133_04();

        int[] prices = {3,3,5,0,0,3,1,4};
//        int[] prices = {1,2,3,4,5};
//        int[] prices = {7,6,4,3,1};

        System.out.println(s.maxProfit(prices));
    }
}

从循环中可以看出，当前天只用到了前一天的结果，显然可采用一维动态数据进行优化，代码如下所示：

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
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution_0133_05 {

    public int maxProfit(int[] prices) {

        // 表示当前天的各个状态
        int[] dp = new int[4];

        // 初始化
        dp[0] = -prices[0];
        dp[1] = 0;
        dp[2] = -prices[0];
        dp[3] = 0;

        for (int i = 1; i < prices.length; i++) {

            dp[3] = Math.max(dp[3], dp[2] + prices[i]);

            dp[2] = Math.max(dp[2], dp[1] - prices[i]);

            dp[1] = Math.max(dp[1], dp[0] + prices[i]);

            dp[0] = Math.max(dp[0], -prices[i]);
        }

        return dp[dp.length - 1];
    }


    public static void main(String[] args) {

        Solution_0133_05 s = new Solution_0133_05();

//        int[] prices = {3,3,5,0,0,3,1,4};
//        int[] prices = {1,2,3,4,5};
        int[] prices = {7,6,4,3,1};

        System.out.println(s.maxProfit(prices));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。

文章作者: 浮云
文章链接: https://ihianian.github.io/2022/06/24/LeetCode-133-BestTimeToBuyAndSellStockIII/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
LeetCode
赏
  目录