題目描述

風(fēng)口之下，豬都能飛。當(dāng)今中國(guó)股市牛市，真可謂“錯(cuò)過(guò)等七年”。 給你一個(gè)回顧歷史的機(jī)會(huì)，已知一支股票連續(xù)n天的價(jià)格走勢(shì)，以長(zhǎng)度為n的整數(shù)數(shù)組表示，數(shù)組中第i個(gè)元素（prices[i]）代表該股票第i天的股價(jià)。 假設(shè)你一開(kāi)始沒(méi)有股票，但有至多兩次買入1股而后賣出1股的機(jī)會(huì)，并且買入前一定要先保證手上沒(méi)有股票。若兩次交易機(jī)會(huì)都放棄，收益為0。 設(shè)計(jì)算法，計(jì)算你能獲得的最大收益。 輸入數(shù)值范圍：2<=n<=100,0<=prices[i]<=100 示例1

輸入

3,8,5,1,7,8

輸出

12

分析：

因?yàn)橐髢纱谓灰缀蟮淖畲笫找?#xff0c;所以先正序掃一遍記錄第k天能獲得的最大收益，然后逆序掃表示第k天之后的區(qū)間能獲得的最大收益，然后相加求最大值

利用動(dòng)態(tài)規(guī)劃的思想。

首先從左往右掃描，先計(jì)算出子序列[0,...,i]中的最大利潤(rùn)，用一個(gè)left數(shù)組保存下來(lái)，時(shí)間是O(n)。第二步是從右往左逆向掃描，計(jì)算子序列[i,...,n-1]上的最大利潤(rùn)，

用right數(shù)組保存下來(lái)，s時(shí)間是O(n)，同時(shí)結(jié)合left和right數(shù)組的結(jié)果就能計(jì)算最終的最大利潤(rùn)了，這一步也是O(n)。?所以最后算法的復(fù)雜度就是O(n)的。

code:

class Solution { public:/*** 計(jì)算你能獲得的最大收益* * @param prices Prices[i]即第i天的股價(jià)* @return 整型*/int calculateMax(vector<int> prices) {int len = prices.size();vector<int> first(101);vector<int> second(101);int temp1=prices[0];first[0]=0;for(int i=1;i<len;i++){temp1=min(temp1,prices[i]);first[i]=max(first[i-1],prices[i]-temp1);}int temp2=prices[len-1];second[len-1]=0;for(int i=len-2;i>=0;i--){temp2=max(temp2,prices[i]);second[i]=max(second[i+1],temp2-prices[i]);}int result=0;for(int i=0;i<len;i++){result=max(result,first[i]+second[i]);}return result;} };

總結(jié)

以上是生活随笔為你收集整理的【小米】风口的猪-中国牛市的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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