Best Time to Buy and Sell Stock III

LeetCode Q 123 - 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 (i.e., you must sell the stock before you buy again).

Example 1:
Input: [3,3,5,0,0,3,1,4] ; Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5] ; Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] ; Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution : DP

State Transfer Function:
dp[k][i] = Math.max(dp[k][i-1], prices[i]-prices[j]+dp[k-1][j-1]) j=[0,1,..i-1]

Code:

public int maxProfit(int[] prices) {
	if (prices == null || prices.length == 0) return 0;
	int[][] dp = new int[3][prices.length + 1];
	for (int k = 1; k <= 2; k++) {
		int max = -prices[0];
		for (int i = 1; i <= prices.length; i++) {
			max = Math.max(max, -prices[i] + dp[k - 1][i - 1]);
			dp[k][i] = Math.max(dp[k][i - 1], prices[i] + max);
		}
	}
	return dp[2][prices.length];
}

Code: Optimize the Time Complexity to O(1)

public int maxProfit(int[] prices) {
	if (prices == null || prices.length == 0) return 0;
	int oneBuyCost = Integer.MIN_VALUE, oneBuyProfit = 0;
	int twoBuyCost = Integer.MIN_VALUE, twoBuyProfit = 0;
	for (int price: prices) {
		oneBuyCost = Math.min(oneBuyCost, price);
		oneBuyProfit = Math.max(oneBuyProfit, price - oneBuyCost);
		twoBuyCost = Math.max(twoBuyCost, -price + oneBuyProfit);
		twoBuyProfit = Math.max(twoBuyProfit, price + twoBuyCost);
	}
	return twoBuyProfit;
}

Here, the oneBuyCost keeps track of the lowest price, and oneBuyProfit keeps track of the biggest profit we could get.
Then the tricky part comes, how to handle the twoBuyCost? Why twoBuyCost = Math.max(twoBuyCost, -price + oneBuyProfit);? Suppose in real life, you have bought and sold a stock and made $100 dollar profit. When you want to purchase a stock which costs you $300 dollars, how would you think this? You must think, um, I have made $100 profit, so I think this $300 dollar stock is worth $200 FOR ME since I have hold $100 for free.
There we go, you got the idea how we calculate twoBuyCost!! We just minimize the cost again!! The twoBuyProfit is just making as much profit as possible.