123. Best Time to Buy and Sell Stock III

这道题还是有点难想的。。。关键在于限制了“买入-卖出”只能两次，之前的greedy策略就不能用了，因为局部的最优很可能不是全局最优，不能股票一开始下跌就卖出，因为以后可能有更高点。

我最开始的思路是，既然我们已经做过题目121. Best Time to Buy and Sell Stock了，已经有办法求出一段数组中的最大利润。那是不是只要在prices[]数组中找到一个点，分别求出这个点两侧的最大利润，使利润之和最大化就可以了？关键是要怎么找出这个点，简单点么就是暴力尝试，于是有了第一个解法：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;

        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            // 分别求这个点两侧的最大利润
            int part1 = innerProfit(prices, 0, i);
            int part2 = innerProfit(prices, i, prices.length);
            max = Math.max(max, part1 + part2);
        }

        return max;
    }

    // 这个函数其实就是题目121. Best Time to Buy and Sell Stock稍微改改
    // 找出数组中某一段的最大利润
    public int innerProfit(int[] prices, int begin, int end) {
        int lastValue = prices[begin]; // 上一个值
        int maxProfit = 0;
        int lowValue = prices[begin]; // 目前的最小值

        for (int i = begin; i < end; i++) {
            int value = prices[i];
            // 上升趋势时，计算最大利润
            if (value > lastValue) {
                maxProfit = Integer.max(maxProfit, value - lowValue);
            }
            // 下降趋势时，找机会替换最小值
            else if (value < lowValue) {
                lowValue = value;
            }
            lastValue = value;
        }

        return maxProfit;
    }
}

这算法是O(N^2)的，结果是毫无疑问的TLE。。。

于是沿着这个思路继续思考，有没有什么办法可以剪枝呢？也许有些计算是多余的。结果还真想到一些诀窍。。。假设我们是数组长度是j吧，然后在第i点切分，变成两个小数组[0,i)和[i,j)，然后计算这种情况下的最大利润。计算完毕后，i要向右“移动”，但移动到哪里呢？之前是直接i++移动一位的。

实际上，i是可以向右移动更多的。如果[i,j)这段我们找到的最大利润是第t天买入，第k天卖出，其中i<t<k<j，那i可以直接移动到t的位置。因为即使i移动到[i,t)之间，右侧的最大利润也不会变了，总的最大利润只会小于等于移动到t时的最大利润。其实道理很简单，仔细想想就能明白。

于是乎又有了第二个解法：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;

        int max = 0;
        for (int i = 0; i < prices.length;) {
            // 基本思路和之前是一样的，找一个点将数组分成两段
            Profit part1 = innerProfit(prices, 0, i);
            Profit part2 = innerProfit(prices, i, prices.length);
            // 如果价格一直是下降的，就没必要再试了
            if (part1.profit == 0 && part2.profit == 0)
                break;
            max = Math.max(max, part1.profit + part2.profit);
            if (part2.a > i)
                i = part2.a;  // 这步是关键
            else
                i++;
        }

        return max;
    }

    // 返回最大利润的同时，还要返回最大利润对应的两个点
    public Profit innerProfit(int[] prices, int begin, int end) {
        if (end - begin <= 1) {
            return new Profit(0, begin, begin);
        }
        int lastValue = prices[begin]; // 上一个值
        int maxProfit = 0;
        int lowValue = prices[begin]; // 目前的最小值

        // 在a点买入，在b点卖出，就能获得最大收益，要算出a和b的值
        int a = begin, b = begin;
        int currentA = begin; // 一个临时变量

        for (int i = begin + 1; i < end; i++) {
            int value = prices[i];
            // 上升趋势时，计算最大利润
            if (value > lastValue) {
                int tmp = value - lowValue;
                if (tmp > maxProfit) {
                    a = currentA;
                    b = i;
                    maxProfit = tmp;
                }
            }
            // 下降趋势时，找机会替换最小值
            else if (value < lowValue) {
                lowValue = value;
                currentA = i;
            }
            lastValue = value;
        }

        return new Profit(maxProfit, a, b);
    }

    // 一个辅助类
    class Profit {
        int profit;
        int a;
        int b;

        public Profit(int profit, int a, int b) {
            this.profit = profit;
            this.a = a;
            this.b = b;
        }

        public String toString() {
            return profit + ", " + a + ", " + b;
        }
    }
}

结果就是代码越来越复杂了。。。其实还是有些bad case的，如果曲线一直是上升的，这个算法会“退化”回第一个版本。

这个解法虽然能AC，但是只能beats 0.07% of java submissions。。。我看到这个都笑了，第一次看到这么低的。。。AC实属侥幸，应该还是我的思路有问题。

看了看其他人的解法，最正常的解法就是dp了：

• 状态定义：dp[i][j]代表如果可以有i次操作，那么在第j天最多可以获得多少利润
• 初始状态：dp[0][j]全是0，同理dp[i][0]也全是0
• 状态转换：dp[i,j] = max(dp[i][j-1], max(prices[j] - prices[t] + dp[i-1, t])) 其中t是[0,j)之间的某个数字其中的原理仔细想想就能明白。如果我要用i次操作在第j天获取最大利润，那么我有两种选择：第j天不做操作，把i次操作在之前全用掉，这时的最大利润就是dp[i][j-1]；或者我留一次操作到第j天，这天卖出股票，假设我是这天卖出的是第t天买入股票，那我今天能拿到的利润是prices[j] - prices[t]，再加上我之前的操作获取的利润（用i-1次操作在第t天能获取的最大利润），就是dp[i-1, t]。求出的prices[j] - prices[t] + dp[i-1, t]最大值就可以了。

关键在于，t怎么找？其实观察下这个状态方程就可以知道是有问题的，因为当前状态不是依赖于有限的历史状态。如果按这个思路去写，大概是这样：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;
        // 只计算两次操作的情况
        return maxProfitWithDP(2, prices);
    }

    public int maxProfitWithDP(int k, int[] prices) {
        // dp[i][j]代表如果可以有i次操作，那么在第j天最多可以获得多少利润
        int[][] dp = new int[k + 1][prices.length];

        // dp[0][j]全是0，同理dp[i][0]也全是0
        // 不显式初始化了，反正int的默认值就是0

        // 开始计算dp矩阵
        for (int i = 1; i < k + 1; i++) {
            for (int j = 1; j < prices.length; j++) {
                // 取两种情况的最大值：
                // 1. 不在第j天卖出股票，就是dp[i][j - 1]
                // 2. 在第j天卖出股票，这个计算就蛋疼了，需要又一次循环

                // 如果我在第j天卖出股票，那这个股票是哪天买的？暴力尝试
                int max = 0;
                for (int t = 0; t < j; t++) { // 第t天买股票，第j天卖出
                    max = Math.max(dp[i - 1][t] + prices[j] - prices[t], max);
                }

                dp[i][j] = Math.max(dp[i][j - 1], max);
            }
        }

        return dp[k][prices.length - 1];
    }
}

这个解法又是O(N^2)的，甚至比我第一个版本的解法还慢，都不用提交就知道肯定要TLE。关键在于第三个for循环，寻找t的那个过程，是否有些计算可以精简？其实是有的：

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1)
            return 0;
        return maxProfitWithDP(2, prices);
    }

    public int maxProfitWithDP(int k, int[] prices) {
        int[][] dp = new int[k + 1][prices.length];
        for (int i = 1; i < k + 1; i++) {
            int tmp = dp[i - 1][0] - prices[0];  // 保存dp[i - 1][t] - prices[t]最大值的临时变量
            for (int j = 1; j < prices.length; j++) {

                // 我的目的是让dp[i - 1][t] + prices[j] - prices[t]尽可能大
                // 而在这一次循环里，prices[j]是固定的，所以我只需要让dp[i - 1][t] - prices[t]尽量大
                // 而在[0,j)这个区间内，dp[i - 1][t] - prices[t]的最大值其实也是固定的，不用每次都通过for循环去算

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

                // 这个最大值不用通过for循环去算
                tmp = Math.max(tmp, dp[i - 1][j] - prices[j]);
            }
        }

        return dp[k][prices.length - 1];
    }
}

这个解法是O(k*N)的，其中k是允许的操作次数。提交后能beats 63.51%了，终于心安了。。。

话说，DP还是挺难想到的。有些题目一眼就能看出来是DP，但有些就很难看出来，挺佩服其他人的脑洞的。。。

再话说，我的那个解法虽然能AC，但可以看到其实没有使用什么额外的空间。这一般是有问题的，从刷题的角度来说，大多数题目都是空间换时间。我们对时间复杂度的关心远超过空间。如果没使用额外的空间，意味着你很可能要TLE。。。