首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
admin
2014-07-18
49
问题
已知一个由正数组成的序列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://kaotiyun.com/show/94xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析西周衰亡的原因。
美国总统提出“十四点原则”的实际目的是()
20世纪初,革命派与改良派论战的中心问题是()。
连续五期用全部或大部分的篇幅报道和评论了五四运动这一伟大运动的杂志是()。
下列选项中,控制了西域政权的是()
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
解析两个战场的地位、作用及相互关系。
魏晋南北朝的手工业技术有所进步,下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
某同学在校园网访问因特网,从该同学打开计算机电源到使用命令ftp202.38.70.25连通文件服务器的过程中,()协议可能没有使用到。
随机试题
EXCEL中,每一个工作簿系统都隐含______个工作表。()
下列哪项不是继发性腹膜炎病因
说唱老艺人王某经多年搜集、整理,将一民间传说创作成评书《花木兰》,同时录制成磁带。《花木兰》在电台播出时,作家曹某逐段录音,并根据录音记录成书,出版了同名小说《花木兰》,署名为曹某。对此,不符合著作权法的规定的是:()
个人汽车贷款的受理是指从客户向银行提交借款申请书、银行受理到上报审核的全过程。()
假设某商业银行以市场价值表示的简化资产负债表中,资产A=1000亿元,负债L=800亿元,资产久期为DA=5年,负债久期为DL=4年。根据久期分析法,如果年利率从5%上升到5%,则利率变化对商业银行的资产价值影响AVA为()亿元。
下列关于老年人年龄的说法中,正确的是()。
一个生产大队有猪、牛、羊各若干头。牛的头数的10倍减去羊的头数再减4,结果再乘以10.正好比猪、牛、羊的总数多4。如果猪、牛、羊的头数均是质数,这个生产队有猪、牛、羊共多少头?
奥苏伯尔认为学生所有的指向学业的行为都可以从三个方面的内驱力进行解释,下面不能由奥苏伯尔提出的内驱力进行解释的学习情形是
Languageisacognitionthattrulymakesushuman.Whereasotherspeciesdocommunicatewithinnateabilitytoproducea【S1】____
A、Hehasbookedatourwiththeagent.B、Hisnephewwantstobookatourwiththeagent.C、Hewantstohavesomeadvicefromthe
最新回复
(
0
)