首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有n个不全为负的整型元素存储在一维数组A[n]中,它包含很多连续的子数组,例如数组A={1,一2,3,10,一4,7,2,一5},请设计一个时间上尽可能高效的算法,求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3,10,一4,7,2},因此
设有n个不全为负的整型元素存储在一维数组A[n]中,它包含很多连续的子数组,例如数组A={1,一2,3,10,一4,7,2,一5},请设计一个时间上尽可能高效的算法,求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3,10,一4,7,2},因此
admin
2018-07-17
42
问题
设有n个不全为负的整型元素存储在一维数组A[n]中,它包含很多连续的子数组,例如数组A={1,一2,3,10,一4,7,2,一5},请设计一个时间上尽可能高效的算法,求出数组A的子数组之和的最大值(例如数组A的最大的子数组为{3,10,一4,7,2},因此输出为该子数组的和18)。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
采用动态规划法。若记 [*] 则所求最大子段和为: [*] 由b[j]的定义可知,当b[j—1]>0时,b[j]=b[j—1]+a[j],否则b[j]=a[j]。 由此可计算b[j]的动态规划递归式:b[j]=max{b[j—1]+a[j],a[j]),1≤j≤n,据此,可设计出求最大字段和的算法如下: 算法思想如下: 不妨对数组元素进行一次遍历,下面是选取一个元素加入子段的一般方法: 倘若一个子段和为b,那么判断下个元素a[k+1]的标准应该为b+a[k+1]≥0(因为当b<0时,任意一
解析
转载请注明原文地址:https://kaotiyun.com/show/F8Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
1979年3月,邓小平在中央理论工作务虚会上首次明确提出必须坚持()。
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
下列关于清朝军机处的叙述,不正确的是()。
经过多年较量,明政府认为起义军中“最强无过闯王”,这里闯王指的是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
下列人物中哪个不属于关学学派?()
清初,著名学者()在抗清活动失败后东渡日本,讲学授徒,培养了大批学者,传播了中国文化。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
随机试题
关于阴道发育异常,下列哪项是正确的
某工程场地进行单孔抽水试验,地层情况及滤水管位置如图4.6.2所示,滤水管上、下均设有止水装置。已知钻孔深度12.0m,承压水位-1.50m,钻孔直径800mm,影响半径R=80m。当降深2.1m时,涌水量Q=510m3/d。试问:用裘布依公式计算其渗透系
2010年8月16日9时47分,黑龙江省伊春市华利实业有限公司(以下简称华利公司)发生特别重大烟花爆竹爆炸事故,共造成34人死亡,2人失踪、152人受伤,直接经济损失6818万元。事故的直接原因:华利公司礼花弹合球工在生产礼花弹,进行合球挤压、敲实礼花弹球
社会学收集资料的四种方法,正确的是()。
因证券公司融资融券交易信息系统故障致使交易中断、监控失效而导致承担客户资产损失的赔偿责任或无法收回到期债权的风险为()。
班主任的工作重点和最经常的工作是()。
【2009-34】首先提出“教育的心理学化”主张的学者是()。
下列关于宋初折杖法的说法,错误的是()。
设f(x)是连续函数,则=__________.
如果运行一个表单,下列事件首先被触发的是()。
最新回复
(
0
)