算法设计与分析 课件 10.2-综合应用-最大字段和问题

信息工程大学算法设计与分析综合应用—最大子段和问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版已知某支股票连续若干天的价格，问：这段时间内，应该在哪天买入哪天卖出才能获得最大收益？天0123456789101112131415价格1001131108510510286638110194106101799490表1：某支股票的价格变动情况思路一：找最低价和最高价思路一：最低价买入，最高价卖出。不正确最低价出现在第7天，最高价出现在第1天。思路二思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。正确吗？1343思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。不正确反例：如下表中的最大收益是第2天买入、第3天卖出，与最低价和最高价无关。天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)思路四：从价格变化的角度考虑，最大收益等价于连续区间的价格变化之和最大的。表3：某支股票的价格变动情况天0123456789101112131415价格p1001131108510510286638110194106101799490变化a13-3-2520-3-16-231820-712-5-2215-4用a[i]表示第i天与前一天的价格差，则最大收益为给定一个序列，找连续区间中和的最大值。最大子段和例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.以上都不对穷举法：计算所有连续区间的和，找其中最大的。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)穷举法改进：去除重复计算，优化连续区间的求和方法。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;}动态规划：用dp[i]表示以第i项结尾的最大子段和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动态规划：用dp[i]表示以第i项结尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整个问题的最大子段和为：max(dp[i],0)。/*动态规划求解最大子段和*/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，则舍弃，否则继续累加，记录其中的最大值。下标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，则舍弃，否则继续累加，记录其中的最大值。

从价格变化的角度考虑，问题等价于求解连续序列的最大和，抽象为最