算法設計與分析 課件 10.2-綜合應用-最大字段和問題

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

ThisSum=0;7.

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

ThisSum+=a[j];9.

if(ThisSum>MaxSum)10. MaxSum=ThisSum;11.}12}13. returnMaxSum;14.}時間復雜度為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){/*如果序列長度為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;}動態(tài)規(guī)劃：用dp[i]表示以第i項結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個問題的最大子段和為：max(dp[i]，0)。下標123456a[i]-2011-413-5-2dp[i]-20117152013動態(tài)規(guī)劃：用dp[i]表示以第i項結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個問題的最大子段和為：max(dp[i],0)。/*動態(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.}時間復雜度為O(n)在線算法：從第1項開始，依次累加后面的項，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。下標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.}時間復雜度為O(n)在線算法：從第1項開始，依次累加后面的項，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。

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