Lexi's Leetcode solutions

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

Posted on: October 19, 2013

有点后悔,这个题当时看了就好了,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;
	}

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

题目里面好像没有说不可以当天买卖,只是说同一时间不能有多次交易。当天只要先把手上股票卖掉,就可以买进了吧?

这里指的同一时间单位应该是天,要不这题就没意思了吧

当天买卖的话,结果不就等于当天没有进行买卖?利润就是第一次买进和第二次卖出的差值。两次买卖相当于只做了一次买卖。

CC150里还有拓扑排序?请教是哪道?大概介绍个关键词我查查也行… 看来我读书不够细啊:(

你好,这么久才回复不好意思啊。。我记得是medium或者hard那两章的某道题,关于图的

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: