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

信息工程大学算法设计与分析综合应用—最大子段和问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

已知某支股票连续若干天的价格，问：这段时间内，应该在哪天买入哪天卖出才能获得最大收益？天0123456789101112131415价格1001131108510510286638110194106101799490表1：某支股票的价格变动情况

思路一：找最低价和最高价思路一：最低价买入，最高价卖出。不正确最低价出现在第7天，最高价出现在第1天。

思路二思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。正确吗？1343

思路二：找最低价和最高价，从最高价向左找最低价，从最低价向右找最高价，取两对价格中差值最大者。不正确反例：如下表中的最大收益是第2天买入、第3天卖出，与最低价和最高价无关。天01234价2：某支股票的价格变动情况

思路三：穷举法，计算所有前后两天的价格差，找最大的，即为最大收益。表1：某支股票的价格变动情况天0123456789101112131415价格1001131108510510286638110194106101799490intmax_value=0;fori=0ton-1forj=i+1ton{t=p[j]-p[i];if(tmax_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(ThisSumMaxSum)MaxSum=ThisSum;12.}13. returnMaxSum;14.}时间复杂度为:O(n3)

穷举法改进：去除重复计算，优化连续区间的求和方法。1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5for(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(ThisSumMaxSum)