[leetcode] Best Time To Buy And Sell Stocks 3 | 股票问题，最多两次买卖，求最大利润

Posted by: lexigrey on: October 19, 2013

In: leetcode
5 Comments

有点后悔，这个题当时看了就好了，T家真的就考了类似的。要是看了就不至于现场出现当天同时买卖那个bug；从后往前scan array也不会那么生疏。。G家也是，要是看了CC150那道题就不会挂在拓扑排序上。没事，记住教训就好了——题是不能越过去的，越是skip的越有考的可能。

这个题一开始是二分法做的，每次切一刀然后左边O(n)做一次右边O(n)做一次，整体是O(n^2)，超时。正确方法是一维dp从左到右扫一遍，再从右到左扫一遍，然后两次加和。
两个一维数组的定义一定要搞清，onsite的时候就栽在这上面了！

d[i]: [0…i]这段时间的买卖一次的最大利润。所以i应该从1开始。
f[i]: [i…n – 1]这段时间的买卖一次的最大利润。所以i应该最大n – 2。
然后就看出问题了——两个i不能同步，否则就当天买卖了。最后加和的时候要错开。
因为“最多买卖两次”，所以还要包括买卖一次的情况。用d[n-1]就是[0…n-1]可以表达这种情况。

        public int maxProfit(int[] prices) {
	    if (prices.length == 0)
	        return 0;
	    int[] d = buildMaxProfitFromStart(prices);
	    int[] f = buildMaxProfitFromEnd(prices);
	    int maxProfit = d[prices.length - 1]; 
	    for (int i = 0; i < prices.length - 1; i++) { 			
                maxProfit = Math.max(maxProfit, d[i] + f[i + 1]); 		
            } 		
            return maxProfit; 	
        } 	
        private int[] buildMaxProfitFromEnd(int[] arr) { 		
            int[] f = new int[arr.length]; 		
            f[arr.length - 1] = 0; 		
            int max = arr[arr.length - 1]; 		
            int maxProfit = 0; 		
            for (int i = arr.length - 2; i >= 0; i--) {
	        maxProfit = Math.max(maxProfit, max - arr[i]);
		max = Math.max(max, arr[i]);
		f[i] = maxProfit;
	    }
	    return f;
	}
	private int[] buildMaxProfitFromStart(int[] arr) {
	    int[] d = new int[arr.length];
	    d[0] = 0;
	    int min = arr[0];
	    int maxProfit = 0;
	    for (int i = 1; i < arr.length; i++) {
	  	maxProfit = Math.max(maxProfit, arr[i] - min);
		min = Math.min(min, arr[i]);
		d[i] = maxProfit;
	    }
	    return d;
	}