首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
admin
2014-07-18
60
问题
已知一个由正数组成的序列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
学硕统考专业
相关试题推荐
鸦片战争后中国社会思想领域发上了哪些重要变化。
评析义和团运动失败的原因及其历史意义。
被马克思称颂为“古代无产阶级的真正代表”的是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
在1956年4月提出实现马克思主义同中国实际“第二次结合”任务的是()。
晚清时期下列武装力量出现的先后顺序是
张仲景的代表性著作是()。
简述西欧经济一体化的原因、进程和意义。
明清两朝已经是中国封建社会的晚期,同时也出现了许多新的社会现象,最明显的是()。
随机试题
阳明潮热的特征为湿温潮热的特征为
肱骨外上髁炎首选的治疗方法是
(各类抗高血压药物的作用)A.缬沙坦B.呋塞米C.哌唑嗪D.阿替洛尔E.硝普钠属于血管紧张素Ⅱ受体阻断剂的是
下图所示建筑的名称依次是:
在如图所示电路中,开关S闭合后,金属环A()。
当会员(客户)出现()情形之一时,交易所有权对其持仓进行强行平仓。
下列关于商品流通企业库存有利作用的表述,错误的是()。
如果某一审计项目的审计风险为5%,注册会计师评估的认定层次重大错报风险为30%,则检查风险应为()。
在分页式系统中,分页由()实现。
WhatisGeorgeOrwellmainlyknownas?
最新回复
(
0
)