123. 买卖股票的最佳时机 III

Problem: 123. 买卖股票的最佳时机 III

思路

你选用何种方法解题？

本题要完成最多两笔交易，而且一次只能持有一支股票，两笔交易不能够有重叠的时间，因此我的想法是，如何把题目规模变小，从而转化为最多只能进行一笔交易的情况，而这个情况之前我们已经用动态规划解决了。

由于最多是两笔交易，我们可以分别从左边开始和从右边开始进行计算最多进行一次交易的最大收益，在计算完成后，我们只需遍历数组，求出截止到i点从左开始计算和从右开始计算的最大收益和，并返回最大收益即可。

一个实现细节是，对于从右开始的计算，我们保存的是最大股票价格而不是最小的，因为虽然从右往左计算，动态规划的值仍然是从区间左边开始，截止到右边的单次股票交易最大收益，而不是反过来的。

一个小小的优化是，在我们做完从左开始的计算后，对于从右开始的计算我们就不必再新开一个dp数组了，可以直接利用原来dp数组的空间，同时也不需要再多遍历一次，原地求两向相加最大收益即可。

复杂度

• 时间复杂度: $O(n)$：遍历两遍数组，n为数组长度。
• 空间复杂度: $O(n)$：n为数组长度。

Code

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int temp = prices[0];
        int [] dp = new int[n];
        dp[0] = 0;
        for (int i = 1;i < n; i++) {
            temp = Math.min(temp, prices[i]);
            dp[i] = Math.max(dp[i - 1], prices[i] - temp);
        }
        int ans = dp[n - 1];
        temp = prices[n - 1];
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            temp = Math.max(temp, prices[i]);
            ans = Math.max(ans, dp[i] + dp[i + 1]);
            dp[i] = Math.max(dp[i + 1], temp - prices[i]);
        }
        return ans;
    }
}