首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
admin
2014-07-18
61
问题
已知一个由正数组成的序列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
学硕统考专业
相关试题推荐
论述中国古代历史上北方少数民族南进的周期性原因及其影响。(南开大学2014年中国历史真题)
下列关于胡司战争的叙述错误的一项是()。
下列选项中,不是由晁错提出的是()
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
简述西欧经济一体化的原因、进程和意义。
明清两朝已经是中国封建社会的晚期,同时也出现了许多新的社会现象,最明显的是()。
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
随机试题
系统
下列属于人工辅助能的是()
甲知其房屋南边邻地将建一高层楼房,但佯装不知,将房屋售给乙。半年后,南边高楼建成,乙之房屋得不到阳光照射。此例中甲违反了民法的()
碳酸氢钠与盐酸中和时所产生的二氧化碳可导致
以“善行而数变”为致病特点的病邪是( )。
村民王某和施某两家相邻。2012年3月,施某在两家之间都不享有宅基地使用权的空地上砌了一堵墙。谁知,这堵墙竟成了两家关系恶化的导火索,围绕砌墙的合法性,砌墙后王家的采光、通风、排水等问题,两家互不相让。5月4日,王某、施某又起纷争,施某先动手打了王某。继而
Despitethegeneralnegativefindings,itisimportanttorememberthatallchildrenwholivethroughadivorcedonotbehavein
在为一个类重载下列运算符时,只能作为该类成员函数重载的运算符是
数据库中有“商品”表如下:要查找出单价高于“0112”的商品记录,正确的SQL命令是()。
MoreandmoreAmericansarereadingtheirowncreditreport.Creditreportsare【B1】______bylenderstodecidehowriskyitwoul
最新回复
(
0
)