2. 考研
  3. 已知一个由正数组成的序列a1，a2，…，an，在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数，我们定义其子段之和为0。如果子段之和为正整数，那么就保留其为子段之和。

已知一个由正数组成的序列a1，a2，…，an，在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数，我们定义其子段之和为0。如果子段之和为正整数，那么就保留其为子段之和。

admin2014-07-18  71
问题 已知一个由正数组成的序列a1，a2，…，an，在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数，我们定义其子段之和为0。如果子段之和为正整数，那么就保留其为子段之和。请设计算法求出序列中的最大子段之和。要求：
  (1)给出算法的主要思想；
  (2)写出算法的实现函数；
  (3)总结所用算法的时间和空间复杂度。
选项
答案(1)本题可以逐次计算每一段的子段之和，然后进行比较，最终得出子段和最大的子段，求出该子段的开始位置和结束为止。 (2)算法的实现过程如下： int Maxsum(int n，int*a，int&besti，int ＆bestj){ ／**本算法用于求出最大子段之和 *返回：最大子段和 *／ int max=0，i，j，tj，tmax，flag，sum； for(i=1；i<=n；i++){ flag=0： sum=0： tmax=*(a+i)；／／tmax暂时保存子段和 for(j=i；j<=n；j++){ if(flag= =0){／／N断是否都是负数 if(*(a+j)>0){ flag=1；／／flag=1时，表示该子段的元素并不是全都是负数 tj=j-1； }else{ tj=j； tmax=0； ／／按照定义全负数之和为0 } } SHill=sum+*(a+j)； if(sum>tmax){ ／／记录下子段和 tmax=sum； fj=j； } } if(tmax>=max){ ／／记录下更大的子段和 max=tmax： besti=i； bestj=tj； } } return max： (3)时间复杂度：O(n2)，空问复杂度与数组个数n无关，因此是0(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/94xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)