【Leetcode】Best Time to Buy and Sell Stock III

Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution

public int maxProfit(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int max = 0;
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        process(nums, left, right);
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, left[i] + right[i]);
        }
        return max;
    }

    public void process(int[] nums, int[] left, int[] right) {
        left[0] = 0;
        right[nums.length - 1] = 0;
        int min = nums[0];
        int max = nums[nums.length - 1];
        //from left, one time
        for (int i = 1; i < nums.length; i++) {
            left[i] = Math.max(left[i - 1], nums[i] - min);
            min = Math.min(min, nums[i]);
        }
        //from right, one time
        for (int j = nums.length - 2; j >= 0; j--) {
            right[j] = Math.max(right[j + 1], max - nums[j]);
            max = Math.max(max, nums[j]);
        }
    }

Result

AC

Analyse

这个思路比较好想出来，因为是两次操作，可以从左边和右边同时开始操作。看的是nums[0….i]和nums[i + 1…..nums.length - 1]之间的两次交易大小，然后再取和。这里的思路是left的求得方法还是从左到右，求得最高的差值，right是从右到左，依次求得最高的差值，如果两者有重合，可以累积起来加成和的形式可以得到两次的最大和值。这里的时间复杂度是O(n)。其实思路还是很稳的，比较容易想出来。

Optimization

public static int maxProfit_(int[] nums) {
        return max(nums, 2);
    }

    public static int max(int[] nums, int k){
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        //local是第i天进行了j次交易,同时最后一天也有交易
        //因此数组的大小设置为len和k + 1
        int[][] local = new int[len][k + 1];
        //global是第i天进行了j次交易
        int[][] global = new int[len][k + 1];

        //最后是这种情况
        //i - 1天进行k - 1次交易

        for (int i = 1; i < len; i++) {
            int diff = nums[i] - nums[i - 1];
            for (int j = 1; j <=k; j++) {
                //global[i - 1][j -1]是i - 1天进行了j - 1次交易, 如果是diff >0, 就是买了i - 1天的,然后第i天出售,
                //如果diff < 0,就是买了i天的,然后第i天出售,那么这样配合前面的global[i - 1][j - 1]就是i - 1天j - 1次交易
                //变成了i天j次交易,而且最后一次交易在第j天.
                //local[i- 1][j]是i - 1天进行了j次交易,而且第j次交易是在i - 1天,那么加上diff的话就是第i - 1天卖出的,等到了第
                //i天卖出,天数多了一天,其实交易次数并没有改变.

                //global[i][j] 是i天进行了j次交易,那么就是 i- 1天进行j次交易,和 i天进行j次交易,并且最后一次交易在第i天进行的,两者的最大值.
                //注意这个地方肯定是交易次数不能改变,从local[i][j]的角度来看就是和不在最后一天交易的比,那么就是global[i- 1][j]

                //local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);


                //当天买了当天卖算一次交易
                //当天买了,第二天卖,第二天买了,第三天卖,算一次交易.
                //i - 1天进行了j - 1次交易
                local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);

                //至于为什么要先求local,再求global,因为是求了local的结果,才得到global的值.
            }
        }
        return global[len - 1][k];
    }

Analyse

这个时间复杂度是O(n*k)，主要是要利用两个思路是设计local和global的用法比较重要。local是利用了交易刚好在最后一天，而global则是全局的交易方案。只有先得到local才能得到全局的结果。