[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++
不過上面這種方式會有點慢

這時候，可以往 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++
在空間的部分，還可以進行一次優化

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

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

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

code 如下
c++
還看到一種解法

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

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

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

kotlin

這邊再來看一個 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