Leetcode - Best Time to Buy and Sell Stock III

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).

 

[balabala] 自己的想法是先找出收益最大的一笔收益，然后从剩余区间中寻找次大的收益，但是在一些case上会失败，比如 [6,1,3,2,4,7]。为什么这种贪婪做法得不到全局最优解呢？如yb君指点，因为第一次交易确定会影响第二次交易的可选范围，子问题之间相互影响，所以不可用最优子问题叠加获取最优解。
正确的思路：至多能做两笔交易，而且交易之间没有重叠，想到可以用divide and conque. 如yb君说，需要综合使用多种算法的题目就会显得比较难。这题就是分治 + 动归 综合题。

 

public class Solution {
    // 以每一天为分界点，分别求出左边和右边能获得的最大收益，然后求出最大值
    // 分治 + 动归
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)
            return 0;
        
        int[] left = new int[prices.length];
        int low = prices[0];
        int maxleft = 0;
        for (int i = 0; i < prices.length; i++) {
            left[i] = Math.max(maxleft, prices[i] - low);
            low = Math.min(low, prices[i]);
        }
        
        int[] right = new int[prices.length];
        int high = prices[prices.length - 1];
        int maxright = 0;
        for (int i = prices.length - 1; i >=0 ;i--) {
            right[i] = Math.max(maxright, high - prices[i]);
            high = Math.max(high, prices[i]); 
        }
        
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxprofit = Math.max(maxprofit, left[i] + right[i]);
        }
    }
    
    ////////////////////////////////下面为不正确思路的实现//////////////////////////////
    //fail @ [6,1,3,2,4,7]
    class ProfitInfo {
        int buyDay;
        int sellDay;
        int profit;
        public ProfitInfo(int buyDay, int sellDay, int profit) {
            this.buyDay = buyDay;
            this.sellDay = sellDay;
            this.profit = profit;
        }
    }
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)
            return 0;
        ProfitInfo profit1 = maxProfit(prices, 0, prices.length - 1);
        ProfitInfo profit2 = maxProfit(prices, 0, profit1.buyDay - 1);
        ProfitInfo profit3 = maxProfit(prices, profit1.sellDay + 1, prices.length - 1);
        return profit1.profit + Math.max(profit2.profit, profit3.profit);
    }
    
    private ProfitInfo maxProfit(int[] prices, int start, int end) {
        if (start >= end) // length of range <= 1
            return new ProfitInfo(start, end, 0);
        int min = start;
        int buy = start;
        int profit = 0;
        int sell = start;
        for (int i = start + 1; i <= end; i++) {
            if (prices[i] < prices[min]) {
                min = i;
            } else if (prices[i] > prices[min]){
                int currProfit = prices[i] - prices[min];
                if (currProfit >= profit) {
                    profit = currProfit;
                    buy = min;
                    sell = i;
                }
            }
        }
        return new ProfitInfo(buy, sell, profit);
    }
    
    // fail @ [2, 4, 1] buy不能同时承担最小价格日以及当前最大profit的购买日，两者不一定是同一个值
    private ProfitInfo maxProfit(int[] prices, int start, int end) {
        if (start >= end) // length of range <= 1
            return new ProfitInfo(start, end, 0);
        int buy = start;
        int profit = 0;
        int sell = start;
        for (int i = start + 1; i <= end; i++) {
            if (prices[i] < prices[buy]) {
                buy = i;
            } else if (prices[i] > prices[buy]){
                int currProfit = prices[i] - prices[buy];
                if (currProfit >= profit) {
                    profit = currProfit;
                    sell = i;
                }
            }
        }
        return new ProfitInfo(buy, sell, profit);
    }
}

 

评论

4 楼 qb_2008 2015-04-24  

我想到的是一维动态规划的扩展，时间复杂度应该是O(n*k)，类似装配链的扩展，从左到右在每个点对所有可能状态找最优值。

3 楼 likesky3 2015-04-23  

这道题确实还有个升级版，求解交易k次的最大利润，想了好久也没想出O(N)的做法……笨方法妥妥地超时

2 楼 likesky3 2015-04-23  

你的实现更简洁些，我遵照你之前教导我的，先写熟练了再考虑简洁代码~ 分治的子问题是完全独立的，但动归中子问题通常伴随有重复，正因为动归存储了子问题结果避免了重复子问题计算从而收获高效。

1 楼 qb_2008 2015-04-23  

局部最优不代表全局最优，找到最赚钱的两笔交易，不代表需要找到最赚钱的那笔交易。因为交易不能重叠。
就像例子[6,1,3,2,4,7]中，最赚钱的一笔交易为[1,7]，但用它全局只能赚6，实际上最赚钱的两笔交易为
[1,3]和[2,7]，全局可以赚7.因为找的第一笔交易会影响第二笔交易的可选范围，子问题间相互影响，所以
不可用最优子问题叠加来得到最优全局解。
最简单的算法O(n^3)，选择两个起点，然后找对应最好的重点。
但实际上因为恰好是两个交易，可以先做出两个数组，用O(n)求解。
MinPrev[i] 代表<=i的最小stock值，MaxPost[i]代表>=i的最大stock值。
int max_earn = 0;
int max_first_earn = 0;
for (i = 0; i < n; ++i) {
  // 以i为第二笔交易的起点，earn为在这种情况下最多赚多少.
  int earn = max_first_earn + MaxPost[i] - s[i];
  max_earn = Max(max_earn, earn);
  max_first_earn = Max(max_first_earn, s[i] - MinPrev[i]);
}
当然，你最上面的解法更清晰，我只是突然想到这一种。我觉得这个不太像分治和动归，
我理解的分治是把问题分解，子问题之间没有任何影响；而动归是把问题规模减小，由子问题组合
出问题解，子问题之间也不会相互影响。
我觉得这道题更像是从求最赚一笔交易的问题延伸而来的。求最赚两笔，就把数组分两截，分别求最赚一笔交易；
求最赚三笔，就把数组分三截，分别求最赚一笔交易。如果不限交易数，似乎是个不错的问题。我似乎发现了
都是O(n)的解法。