一、買賣股票的最佳時機——一次買賣機會

??給定一個代表股票價格的數(shù)組，只能進行一次買賣交易，求所能獲取的最大利潤。例如

A=[7,1,5,3,6,4]

??顯然1時買入，6時賣出，利潤最大。
??數(shù)組Am和An，關(guān)系為Am=[An，m]，令A(yù)n時，最低買入價為i，最高賣出價為o，最大利潤為p=o-i。
??若m<i，因為出現(xiàn)了更低的買入價，則更新最低買入價，i=m。
??而最高賣出價則要每次都更新，因為需要不斷的計算當前的利潤來比較最大值。
??綜上所述，狀態(tài)轉(zhuǎn)換方程為

An = [An-1, n] o = n if(i > n), i = n p = max(p, o-i)

??代碼如下

int maxProfit(int* prices, int pricesSize) {int in = prices[0];int profits = 0;int i = 0;for(i=1; i<pricesSize; i++){if(prices[i] < in)in = prices[i];profits = profits>(prices[i]-in)?profits:prices[i]-in;} return profits; }

二、買賣股票的最佳時機——多次買賣機會

??給定一個代表股票價格的數(shù)組，進行多次買賣交易，求所能獲取的最大利潤。
??例如，A=[7,1,5,3,6,4]，1時買入，5時賣出，3時買入，6時賣出，利潤最大。
??感覺比上題更簡單，只要后面的賣出價高于買入價就交易，然后把利潤相加。唯一需要注意的是當賣出后，需要把賣出價記錄為新的買入價。
??狀態(tài)轉(zhuǎn)化方程

An = [An-1,n] if(in > n), in = n if(in < n), out = n p += out-in in = out

??代碼如下

int maxProfit(int* prices, int pricesSize) {int in = prices[0];int profits = 0;int i = 0;for(i=1; i<pricesSize; i++){if(prices[i] > in)profits += (prices[i]-in);in = prices[i]; } return profits; }

總結(jié)

以上是生活随笔為你收集整理的动态规划—1.2 买卖股票的最佳时机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。