买卖股票的最佳时机III

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

LeetCode每日一题，123. Best Time to Buy and Sell Stock III

先看题目描述

sMVf5F.png

还是股票交易问题，给定数组 prices 表示股票每天的价格，限制最多进行两笔交易，问最大收益是多少

算法和思路

动态规划

这题实际上是 买卖股票的最佳时机IV 中 k = 2 的情况，是那道题的简化版，直接套用里面的代码，令 k = 2 就可以

算法源码

动态规划

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
class Solution {
    public int maxProfit(int[] prices) {
        int k = 2;
        int len = prices.length;
        k = Math.min(k, len / 2);
        if (k == 0) {
            return 0;
        }
        int[][] buy = new int[len][k + 1];
        int[][] sell = new int[len][k + 1];
        Arrays.fill(buy[0], Integer.MIN_VALUE / 2);
        Arrays.fill(sell[0], Integer.MIN_VALUE / 2);
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i][0] = Math.max(buy[i - 1][0], -prices[i]);
            for (int j = 1; j <= k; j++) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(buy[i - 1][j - 1] + prices[i], sell[i - 1][j]);
            }
        }
        int res = 0;
        for (int profit : sell[len - 1]) {
            res = Math.max(profit, res);
        }
        return res;
    }
}

下面是题解的代码，维护了四个状态：只进行过一次买操作；进行过一次买操作和一次卖操作；在完成了第一笔交易的前提下，进行了第二次买操作；完成了全部两笔交易。分别用 buy1，sell1，buy2，sell2 维护这四个状态的最大利润，状态转移方程如下：

  • buy1 = max{buy1，-prices[i]}
  • sell1 = max{buy1 + prices[i]，sell1}
  • buy2 = max{buy2，sell1 - prices[i]}
  • sell2 = max{buy2 + prices[i]，sell2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -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;
    }
}

题解的代码运行效率明显更高