LeetCode 123 Best Time to Buy and Sell Stock III

LeetCode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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).

题目大意：

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

解题思路：

回顾一下前两题：只能进行一次交易和可以无数次交易。分别是用(min, p),sum(prices[i]-prices[i-1])的方法。这题很明显比较接近只能进行一次交易的题。
如果考虑将此问题分为两个子问题(Divide & Conquer,二分法)，prices[0,k]和prices[k,n-1]，只要将k取遍所有值就得到解。

Java代码：

public int maxProfit(int[] prices) {
	int max = 0;
	for(int i=0;i<prices.length;i++){
		int p = maxProfitSingle(Arrays.copyOfRange(prices,0, i+1))
				+ maxProfitSingle(Arrays.copyOfRange(prices,i, prices.length));
		if(max<p)
			max = p;
	}
	return max;
}

算法分析：

时间复杂度为O(n²)，空间复杂度O(1)。

上述解法并非最优，因为计算prices[0,k-1]到prices[0,k]时候再次重复计算用了O(n)，但由只能进行一次交易题解中知道，其实O(1)可得，只要在计算过程中把结果存入left数组中即可。
下面的难点在于计算prices[k,n-1]。右端点固定，从右到左计算，所以其实是只能进行一次交易题解的逆运算并把结果存入到right数组。区别是(max, p)。最后只要遍历left[k]+right[k],即可得到最大利润。

注意事项：

数组长度为0。
二分法
用数组存储重复计算结果(DP)

Java代码：

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	//前i天最大利润，并非需要第i天卖出
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
	
	int min = prices[0], maxPL = 0;
	for(int i=0;i<prices.length;i++){
		int p = prices[i] - min;
		if(maxPL<p)
			maxPL = p;
		left[i] = maxPL;
		if(min>prices[i])
			min=prices[i];
	}
	int max=prices[prices.length-1],maxPR=0;
	for(int j=prices.length-1;j>=0;j--){
		int p=max-prices[j];
		if(maxPR<p)
			maxPR = p;
		right[j] = maxPR;
		if(max<prices[j])
			max=prices[j];
	}
	int maxP = 0;
	for(int k=0;k<prices.length;k++){
		if(maxP<left[k]+right[k])
			maxP = left[k]+right[k];
	}
	return maxP;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

KK's blog

LeetCode 123 Best Time to Buy and Sell Stock III

题目大意：

解题思路：

Java代码：

算法分析：

注意事项：

Java代码：

算法分析：

相关题目：