首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
admin
2014-07-18
79
问题
已知一个由正数组成的序列a
1
,a
2
,…,a
n
,在这个序列中的元素既有正整数也有负整数。我们定义SUM
k,l
=a
k
+a
k+1
+……+a
l
为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为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(n
2
),空问复杂度与数组个数n无关,因此是0(1)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/94xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列哪一项最符合《附益法》的主要内容?()
下列不属于凯末尔主义内容的是()。
近代西方自由主义流派众多,其中功利主义学说代表人物是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
评述从五四运动到中国共产党成立,马克思主义在中国传播的情况及其原因。
试简述当代资本主义经济发展的三个阶段。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
通常所说的32位微处理器是指()。
随机试题
A.氯丙嗪B.奋乃静C.氯氮平D.硫利哒嗪E.丙米嗪几乎无锥体外系反应的药物是
耕地占补平衡考核以建设用地项目为单位进行,主要考核耕地补充方案中确定的补充耕地的数量和()。
以地表水作为饮用水源时,应采用澄清加消毒的处理工艺,其中完善而有效的混凝、沉淀和过滤过程,能够有效地()。
建设工程项目实施阶段组织策划的工作内容包括()。
Excel2013中,在单元格中输人公式时,编辑栏上的“√”按钮表示()操作。
《巴塞尔资本协议》首次提出了资本充足率监管的国际标准,并且提出了合格监管资本的范围。()
下列各项业务,在进行会计处理时不应该计入管理费用的有()。
下列各项中,会引起应收账款账面价值发生变化的有()。
下列哪首作品与琵琶协奏曲《草原英雄小姐妹》的体裁相同?()
3.转基因食品可能带来副作用,但一种转基因大豆含有有益于人体健康的微量元素,专家建议人们食用这种大豆加工成的产品。以下哪项最能支持专家的建议?
最新回复
(
0
)