[LeetCode] 123. Best Time to Buy and Sell Stock III

轉自LeetCode

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

<Solution>

一樣是 Best Time to Buy and Sell Stock 的衍生題

這次的交易次數限制是，至多兩次

直覺想法就是用dfs找出所有組合，把最大利潤記錄下來

code 如下
c++

	class Solution {
	private:
	int ans;
	public:
	int maxProfit(vector<int>& prices) {
	ans = 0;
	dfs(0, 0, 1, prices);
	return ans;
	}
	void dfs(const int sum, const int start, const int level, vector<int>& prices) {
	int profit = 0;
	int minV = INT_MAX;
	for(int i = start; i < prices.size(); i++) {
	if(prices[i] < minV) {
	minV = prices[i];
	}
	else {
	profit = max(profit, prices[i] - minV);
	if(level < 2) {
	dfs(profit, i+1, level+1, prices);
	}
	}
	}
	if(level == 2) {
	ans = max(ans, sum + profit);
	}
	}
	};

view raw bestTimeBuyAndSellStockIII_1.cpp hosted with ❤ by GitHub

不過上面這種方式會有點慢

這時候，可以往 DP 的解法，把之前的結果拿來使用，已達到加速效果

使用DP的時候，最難的是找到公式

在這邊，需要使用兩個變數，一個是局部最優 localMax，以及全局最優 globalMax

兩個變數都是二維陣列，localMax[i][j] 和 globalMax[i][j] 分別代表的意思是

在第 i 天進行第 j 次交易的局部最優和全局最優

先來看 globalMax

globalMax[i][j] = max(globalMax[i-1][j], localMax[i][j])

第i天第j次交易時的全局最優，是前一天第j次交易的全局最優，和今天第j次交易的局部最優，取最大值

而 localMax 如下

int diff = prices[i] - prices[i-1]

localMax[i][j] = max(globalMax[i-1][j-1] + ((diff > 0) ? diff : 0), localMax[i-1][j] + diff)

第i天第j次交易時的全局最優，是前一天第j-1次交易的全局最優，加上前一天買今天賣的這筆交易(如果賺錢的話)

和前一天第j次交易，加上前一天買今天賣的這筆交易(不判斷有沒有賺錢，一律加上去，這樣依然會保持第j次交易)，來取最大值

這邊特別在說明一下 localMax[i-1][j] + diff

例如 [1, 3, 2]，第二天的第一次交易是 3 - 1 = 2，第三天的第一次交易是 2 - 3 = -1

當把這兩天的交易加起來 2 + (-1) = 1，其實還是等同於一次交易而已(第一天買，第三天賣)

找到公式之後就可以寫成 code

code 如下(參考資料1，參考資料2)
c++

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.empty()) {
	return 0;
	}
	const int length = prices.size();
	vector<vector<int>> localMax(length, vector<int>(3, 0));
	vector<vector<int>> globalMax(length, vector<int>(3, 0));
	int diff;
	for(int i = 1; i < length; i++) {
	diff = prices[i] - prices[i-1]; //> final deal is today
	for(int j = 1; j <= 2; j++) {
	localMax[i][j] = max(globalMax[i-1][j-1] + ((diff > 0) ? diff : 0), localMax[i-1][j] + diff);
	globalMax[i][j] = max(globalMax[i-1][j], localMax[i][j]);
	}
	}
	return globalMax[length-1][2];
	}
	};

view raw bestTimeBuyAndSellStockIII_2.cpp hosted with ❤ by GitHub

在空間的部分，還可以進行一次優化

因為沒有要問，一次交易，兩次交易的最佳解分別是什麼

所以可只保留兩次交易的答案就好

那因為覆蓋順序的關係，不能從第一次交易開始算起，得從第二次交易開始算起才會對(global[j-1] 的值才會是對的)

code 如下
c++

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.empty()) {
	return 0;
	}
	const int length = prices.size();
	vector<int> localMax(3, 0);
	vector<int> globalMax(3, 0);
	int diff;
	for(int i = 1; i < length; i++) {
	diff = prices[i] - prices[i-1]; //> final deal is today
	for(int j = 2; j > 0; j--) {
	localMax[j] = max(globalMax[j-1] + ((diff > 0) ? diff : 0), localMax[j] + diff);
	globalMax[j] = max(globalMax[j], localMax[j]);
	}
	}
	return globalMax[2];
	}
	};

view raw bestTimeBuyAndSellStockIII_3.cpp hosted with ❤ by GitHub

還看到一種解法

因為題目有說一定要遵守先買後賣，且第二次買一定要在第一次賣之後

所以可以順著這個邏輯來找最大利潤

code 如下(參考資料)
c++

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	int firstBuy = INT_MAX;
	int profitAfterFirstSell = 0;
	int profitAfterSecondBuy = INT_MIN;
	int profitAfterSecondSell = 0;
	for(const auto p : prices) {
	//> for first buy price ,the lower,the better
	firstBuy = min(firstBuy, p);
	//> the profit after first sell ,the higher,the better
	profitAfterFirstSell = max(profitAfterFirstSell, p - firstBuy);
	//> the profit left after second buy,the higher,the better
	profitAfterSecondBuy = max(profitAfterSecondBuy, profitAfterFirstSell - p);
	// the profit left after second sell ,the higher,the better
	profitAfterSecondSell = max(profitAfterSecondSell, profitAfterSecondBuy + p);
	}
	return profitAfterSecondSell;
	}
	};

view raw bestTimeBuyAndSellStockIII_4.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun maxProfit(prices: IntArray): Int {
	var firstBuyCost = Int.MAX_VALUE
	var profitAfterFirstSell = 0
	var profitAfterSecondBuy = Int.MIN_VALUE
	var profitAfterSecondSell = 0
	for(p in prices) {
	firstBuyCost = Math.min(firstBuyCost, p)
	profitAfterFirstSell = Math.max(profitAfterFirstSell, p - firstBuyCost)
	profitAfterSecondBuy = Math.max(profitAfterSecondBuy, profitAfterFirstSell - p)
	profitAfterSecondSell = Math.max(profitAfterSecondSell, profitAfterSecondBuy + p)
	}
	return profitAfterSecondSell
	}
	}

view raw best_time_to_buy_and_sell_stock_III.kt hosted with ❤ by GitHub

這邊再來看一個 DP 的解法，這種解法也可以用在 188. Best Time to Buy and Sell Stock IV

dp[i][j] 在第 i 次交易在第 j 天的最大利潤

因為在第 j 天賣出，不會增加 transaction count

且一定要先買後賣

所以在每次歷遍價格前，currentProfit = -prices[0]

因此

dp[i][j] = max(do nothing, sell today) = max(dp[i][j-1], currentProfit + prices[j])

而同時間，更新 currentProfit 給 next round 使用

這邊要決定的是，買了會不會讓之後的 profit 更高

currentProfit = max(do nothing, buy today) = max(currentProfit, dp[i-1][j-1] - prices[j])

因為 buy 會增加 transaction count，所以要找 dp[i-1] 的位置來當作 do nothing

kotlin

	class Solution {
	fun maxProfit(prices: IntArray): Int {
	val dp = Array(3) {IntArray(prices.size) {0}}
	var currentProfit = 0
	for(i in 1..2) {
	currentProfit = -prices[0] // you need to buy first
	for(j in 1 until prices.size) {
	// max(do nothing, sell today)
	// sell won't increase transaction count
	dp[i][j] = Math.max(dp[i][j-1], currentProfit + prices[j])
	// this value is for the next round
	// max(do nothing, buy today)
	// buy will increase transaction count
	currentProfit = Math.max(currentProfit, dp[i-1][j-1] - prices[j])
	}
	}
	return dp[2].last()
	}
	}

view raw best_time_to_buy_and_sell_stock_III.kt hosted with ❤ by GitHub