首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
admin
2014-07-18
51
问题
已知一个由正数组成的序列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
学硕统考专业
相关试题推荐
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
我国第一部系统的史学理论著作是()。
蒙古军西征之后,罗斯处于()的控制之下。
秦朝修建的工程中,沟通了中原与岭南经济文化交流的是()
以北宋三大发明为例简述北宋科学技术的特征。
拉美独立后,各国政治上的一种普遍现象是(),实质上它是拉美各国大地主专政的一种特殊形式。
清初,著名学者()在抗清活动失败后东渡日本,讲学授徒,培养了大批学者,传播了中国文化。
著名的网络OSI七层模型是由()组织提出来的。
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
关于因特网中的主机和路由器,以下说法中正确的是()。I.主机通常需要实现TCP协议Ⅱ.路由器必须实现TCP协议Ⅲ.主机必须实现IP协议Ⅳ.路由器须实现IP协议
随机试题
请说明淹塔是怎样造成的。
图示梁[σ]=160MPa,试按正应力强度条件设计图形和矩形两种截面尺寸。
A.酪氨酸酶缺乏B.6-磷酸葡萄糖脱氢酶分子缺陷C.苯丙氨酸羟化酶缺乏D.胆碱酯酶不可逆性抑制E.巯基酶不可逆性抑制有机磷中毒
血清无菌处理兼顾不使蛋白变性,应使用
治疗变异型心绞痛首选
某县破获一抢劫团伙,涉嫌多次入户抢劫,该县法院审理后认为,该团伙中只有主犯赵某可能被判处无期徒刑。关于该案的移送管辖,下列哪些选项是正确的?(2014年卷二66题)
分析对比各治理方案所采用的管理和监测方式的优缺点是指()对比。
不断强化环境污染防治,巩固“三河”水污染治理成果,下列属于“三河”之一的是()。
油品装卸鹤管至油品生产、仓储企业围墙的铁路大门的距离,一般不小于()m。
由于社会对产品的需求量降低使产品销售困难,从而导致生产该产品的设备开工不足,并由此引起设备贬值,这种贬值称为()。
最新回复
(
0
)