【題目描述】
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?k transactions.
?Notice：You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
假設(shè)你有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。
設(shè)計(jì)一個(gè)算法來找到最大的利潤或粮。你最多可以完成?k?筆交易。
【注】你不可以同時(shí)參與多筆交易(你必須在再次購買前出售掉之前的股票)
【題目鏈接】
www.lintcode.com/en/problem/best-time-to-buy-and-sell-stock-iv/
【題目解析】
下面的解法主要是能把兩次的限制推廣到k次交易：
這道題是Best Time to Buy and Sell Stock的擴(kuò)展讯嫂，現(xiàn)在最多可以進(jìn)行兩次交易。所以仍然使用動態(tài)規(guī)劃來完成兆沙，事實(shí)上可以解決非常通用的情況欧芽，也就是最多進(jìn)行k次交易的情況。 這里我們先解釋最多可以進(jìn)行k次交易的算法挤悉，然后最多進(jìn)行兩次我們只需要把k取成2即可渐裸。我們還是使用“局部最優(yōu)和全局最優(yōu)解法”巫湘。我們維護(hù)兩種量装悲，一個(gè)是當(dāng)前到達(dá)第i天可以最多進(jìn)行j次交易，最好的利潤是多少（global[i][j]）尚氛，另一個(gè)是當(dāng)前到達(dá)第i天诀诊，最多可進(jìn)行j次交易，并且最后一次交易在當(dāng)天賣出的最好的利潤是多少（local[i][j]）阅嘶。下面我們來看遞推式属瓣，全局的比較簡單，
global[i][j]=max(local[i][j],global[i-1][j])讯柔，
也就是去當(dāng)前局部最好的抡蛙，和過往全局最好的中大的那個(gè)（因?yàn)樽詈笠淮谓灰兹绻?dāng)前天一定在局部最好的里面，否則一定在過往全局最優(yōu)的里面）魂迄。
全局（到達(dá)第i天進(jìn)行j次交易的最大收益） = max{局部（在第i天交易后粗截，恰好滿足j次交易），全局（到達(dá)第i-1天時(shí)已經(jīng)滿足j次交易）}
對于局部變量的維護(hù)捣炬，遞推式是
local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)熊昌，
也就是看兩個(gè)量，第一個(gè)是全局到i-1天進(jìn)行j-1次交易湿酸，然后加上今天的交易婿屹，如果今天是賺錢的話（也就是前面只要j-1次交易，最后一次交易取當(dāng)前天）推溃，第二個(gè)量則是取local第i-1天j次交易昂利，然后加上今天的差值（這里因?yàn)閘ocal[i-1][j]比如包含第i-1天賣出的交易，所以現(xiàn)在變成第i天賣出，并不會增加交易次數(shù)蜂奸，而且這里無論diff是不是大于0都一定要加上梯捕，因?yàn)榉駝t就不滿足local[i][j]必須在最后一天賣出的條件了）。
局部（在第i天交易后窝撵，總共交易了j次） = max{情況2傀顾，情況1}
情況1：在第i-1天時(shí)，恰好已經(jīng)交易了j次（local[i-1][j]）碌奉，那么如果i-1天到i天再交易一次：即在第i-1天買入短曾，第i天賣出（diff），則這不并不會增加交易次數(shù)赐劣！【例如我在第一天買入嫉拐，第二天賣出；然后第二天又買入魁兼，第三天再賣出的行為 和 第一天買入婉徘，第三天賣出 的效果是一樣的，其實(shí)只進(jìn)行了一次交易咐汞！因?yàn)橛羞B續(xù)性】 情況2：第i-1天后盖呼，共交易了j-1次（global[i-1][j-1]），因此為了滿足“第i天過后共進(jìn)行了j次交易化撕，且第i天必須進(jìn)行交易”的條件：我們可以選擇1：在第i-1天買入几晤，然后再第i天賣出（diff），或者選擇在第i天買入植阴，然后同樣在第i天賣出（收益為0）蟹瘾。
上面的算法中對于天數(shù)需要一次掃描，而每次要對交易次數(shù)進(jìn)行遞推式求解掠手，所以時(shí)間復(fù)雜度是O(n*k)憾朴，如果是最多進(jìn)行兩次交易，那么復(fù)雜度還是O(n)喷鸽≈诶祝空間上只需要維護(hù)當(dāng)天數(shù)據(jù)皆可以，所以是O(k)魁衙，當(dāng)k=2报腔，則是O(1)。
【參考答案】
www.jiuzhang.com/solutions/best-time-to-buy-and-sell-stock-iv/
