算法設(shè)計(jì)與分析 課件 10.2-綜合應(yīng)用-最大字段和問題

信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最大子段和問題國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版已知某支股票連續(xù)若干天的價(jià)格，問：這段時(shí)間內(nèi)，應(yīng)該在哪天買入哪天賣出才能獲得最大收益？天0123456789101112131415價(jià)格1001131108510510286638110194106101799490表1：某支股票的價(jià)格變動(dòng)情況思路一：找最低價(jià)和最高價(jià)思路一：最低價(jià)買入，最高價(jià)賣出。不正確最低價(jià)出現(xiàn)在第7天，最高價(jià)出現(xiàn)在第1天。思路二思路二：找最低價(jià)和最高價(jià)，從最高價(jià)向左找最低價(jià)，從最低價(jià)向右找最高價(jià)，取兩對(duì)價(jià)格中差值最大者。正確嗎？1343思路二：找最低價(jià)和最高價(jià)，從最高價(jià)向左找最低價(jià)，從最低價(jià)向右找最高價(jià)，取兩對(duì)價(jià)格中差值最大者。不正確反例：如下表中的最大收益是第2天買入、第3天賣出，與最低價(jià)和最高價(jià)無關(guān)。天01234價(jià)格10117106表2：某支股票的價(jià)格變動(dòng)情況思路三：窮舉法，計(jì)算所有前后兩天的價(jià)格差，找最大的，即為最大收益。表1：某支股票的價(jià)格變動(dòng)情況天0123456789101112131415價(jià)格1001131108510510286638110194106101799490intmax_value=0;fori=0ton-1forj=i+1ton{t=p[j]-p[i];if(t>max_value)max_value=t;}returnmax_value;時(shí)間復(fù)雜度為O(n2)思路四：從價(jià)格變化的角度考慮，最大收益等價(jià)于連續(xù)區(qū)間的價(jià)格變化之和最大的。表3：某支股票的價(jià)格變動(dòng)情況天0123456789101112131415價(jià)格p1001131108510510286638110194106101799490變化a13-3-2520-3-16-231820-712-5-2215-4用a[i]表示第i天與前一天的價(jià)格差，則最大收益為給定一個(gè)序列，找連續(xù)區(qū)間中和的最大值。最大子段和例1：序列(-20,11,-4,13,-5,-2)的最大子段和為(11,-4,13)=20。例2：序列(-20,11,-4,-6,-5,-2)的最大子段和為(11)=11。例3：序列(-20,-11,-4,-13,-5,-2)的最大子段和為0。選擇題序列(20,11,4,6,5,2)的最大子段和為（）。A.48B.20C.0D.以上都不對(duì)窮舉法：計(jì)算所有連續(xù)區(qū)間的和，找其中最大的。a[i]a[j]1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5. for(i=1;i<=n;i++)/*a[i]為起點(diǎn)*/6. for(j=i;j<=n;j++){/*a[j]為終點(diǎn)*/7. ThisSum=0;8. for(k=i;k<=j;k++)/*累加a[i]~a[j]*/9. ThisSum+=a[k];10. if(ThisSum>MaxSum)MaxSum=ThisSum;12.}13. returnMaxSum;14.}時(shí)間復(fù)雜度為:O(n3)窮舉法改進(jìn)：去除重復(fù)計(jì)算，優(yōu)化連續(xù)區(qū)間的求和方法。1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5

for(i=1;i<=n;i++){/*a[i]為起點(diǎn)*/6.

ThisSum=0;7.

for(j=i;j<=n;j++){/*a[j]為終點(diǎn)*/8.

ThisSum+=a[j];9.

if(ThisSum>MaxSum)10. MaxSum=ThisSum;11.}12}13. returnMaxSum;14.}時(shí)間復(fù)雜度為O(n2)a[i]a[j]a[j+1]分治法：序列一分為二，取三種情況的最大值。情況1：左邊序列的最大子段和情況2：右邊序列的最大子段和情況3：跨越中間位置的最大子段和-2011-4135-2110131120T(n/2)T(n/2)O(n)T(n)=2T(n/2)+cn,T(1)=O(1)=O(nlogn)01376/*分治法求最大子段和*/1.intMaxSum(int*a,intleft,intright){2.intsum=0;3.intcenter=0,leftsum=0,rightsum=0,lefts=0,rights=0,s1=0,s2=0;4.if(left==right){/*如果序列長(zhǎng)度為1，直接求解*/5.

if(a[left]>0)sum=a[left];6.

elsesum=0;7.}else{8.center=(left+right)/2;9.leftsum=MaxSum(a,left,center);/*求左序列的最大子段和*/10.

rightsum=MaxSum(a,center+1,right);/*求右序列的最大子段和*/11.

s1=0;lefts=0;12.for(inti=center;i>=left;i--){/*求中間位置向左的最大和*/13. lefts+=a[i];if(lefts>s1)s1=lefts;}14.s2=0;rights=0;15.for(intj=center+1;j<=right;j++){/*求中間位置向右的最大和*/16.

rights+=a[j];if(rights>s2)s2=rights;}17.sum=s1+s2;18.if(sum<leftsum)sum=leftsum;19.if(sum<rightsum)sum=rightsum; 20.}21.returnsum;}動(dòng)態(tài)規(guī)劃：用dp[i]表示以第i項(xiàng)結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個(gè)問題的最大子段和為：max(dp[i]，0)。下標(biāo)123456a[i]-2011-413-5-2dp[i]-20117152013動(dòng)態(tài)規(guī)劃：用dp[i]表示以第i項(xiàng)結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個(gè)問題的最大子段和為：max(dp[i],0)。/*動(dòng)態(tài)規(guī)劃求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. intMaxSum,i;4. dp[0]=0;5. MaxSum=0;/*MaxSum初始化為0，保證了最大子段和>=0*/6.

for(i=1;i<=n;i++){7. dp[i]=max(dp[i-1]+a[i],a[i]);8.

if(dp[i]>MaxSum)MaxSum=dp[i];9.}10. returnMaxSum;11.}時(shí)間復(fù)雜度為O(n)在線算法：從第1項(xiàng)開始，依次累加后面的項(xiàng)，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。下標(biāo)123456a[i]-2011-413-5-21172015130/*在線算法求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. inttSum,MaxSum,j;4. tSum=MaxSum=0;5. for(j=1;j<=n;j++){6. tSum+=a[j];7. if(tSum>MaxSum)8. MaxSum=tSum;9. elseif(tSum<0)10. tSum=0;11. }12. returnMaxSum;13.}時(shí)間復(fù)雜度為O(n)在線算法：從第1項(xiàng)開始，依次累加后面的項(xiàng)，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。

從價(jià)格變化的角度考慮，問題等價(jià)于求解連續(xù)序列的最大和，抽象為最