LeetCode 股票系列（二）

今天我们来继续聊聊 Leetcode 的华尔街之狼（The Wolf of Wall Street）系列，也称股票系列， 在 Leetcode 上有 6 题之多。

今天讲解的是第二题，与第一题相比升级了一点难度，我们一起来看下。

2. Best Time to Buy and Sell Stock III

与第一题类似，给你一组数组 prices=[3,3,5,0,0,3,1,4]。

prices[i] 代表在第 i 天股票的价格，可以进行买卖操作，但得先买了才能卖。

这一次，你最多进行2次买与卖的操作，问你能够赚到的最大收益是多少？

比如这个例子中，我们在第四天买第六天卖，和在第七天买第八天卖，我们可以得到 (3-0)+(4-1)=6，这是我们能得到的最大收益。

问题分析 ：

这道题升级了一点难度，可以进行两次的交易，但是只要打好了第一题的基础，这题也并不会太难的。

我们已经通过了第一题学会了如何计算最多进行一次买卖操作的最大利润，我们将通过已经计算好的一次交易最大利润去计算两次的是多少。

假设我们第一次 卖 发生在 i，那么我们第一次交易得发生在 prices[0 : i]， 而我们第二次交易得发生在 prices[i+1 : n]。

• 对于第一次交易，我们可以像第一题的 方法 3 一样，我们枚举每一次卖，我们只需要再找到 prices[i+1 : n] 的一次最大利润操作即可。
  
• 对于 prices[i+1 : n] 这一段，我们可以枚举买，如果买发生在 prices[i]，那么卖得发生在 prices[i+1 : n]。
  

方法1：

public int maxProfit(int[] A) {
        int n = A.length;
        int maxProfit = 0;
    //dp[i] 代表 prices[i:n] 能得到的最大一次交易利润，也就是我们的第二次操作。
        int dp[] = new int[n];
        int maxSell = A[n-1];
        for (int i = n - 2; i >= 0; i--) {
        //maxSell-A[i] 代表如果我们在i这天进行购买的话的最大利润
            dp[i] = Math.max(dp[i+1], maxSell - A[i]);
            maxSell = Math.max(maxSell, A[i]);
            maxProfit = Math.max(maxProfit, dp[i]);
        }
        int minBuy = A[0];
        for (int i = 1; i < A.length - 1; i++) {
        //假设我们第一次卖发生在i,买得发生在prices[0:i-1]
        //第二次操作发生在prices[i+1 : n]，dp[i+1]表示prices[i+1 : n]这段区间进行一次操作的最大值
            maxProfit = Math.max(maxProfit, dp[i + 1] + (A[i] - minBuy));
            minBuy = Math.min(minBuy, A[i]);
        }
        return maxProfit;
    }

代码总结：

• 我们枚举第一次的卖发生在 i，那么第一次操作发生在prices[0 : i]，而第二次操作发生在 prices[i+1 : n]。
• 我们可以提前对 prices[i+1 : n] 进行提前处理。
• dp[i] 代表 prices[i : n] 最大利润的一次交易，我们可以像第一题的题解3一样去枚举买
• 再枚举第一次交易的卖，如果它发生在 i，我们能得到的最大利润就是prices[i] - min(prices[0 : i-1]) + dp[i+1]

空间复杂度和时间复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)