首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
27
问题
设有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
学硕统考专业
相关试题推荐
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
提出电磁感应定律的是物理学家()。
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
詹天佑自主设计修建了中国第一条铁路是在()。
十字军东征的目标是解放圣地()。
洪武八年。朱元璋仿照元朝的办法,印造(),命令民间通行。形成了钱、钞并用的货币制度。
周王室的两大官僚系统是()。
加尔文教传播到法国后,其信仰者被称为()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
随机试题
A.小活络丹B.补阳还五汤C.当归四逆汤D.黄芪桂枝五物汤E.阳和汤
A.抗炎B.镇静C.利尿D.解热E.利胆祛风湿药的主要药理作用是()
兴奋剂目录所列的禁用物质包括()。
通知行审证和卖方审证是审证的两个环节,其中卖方审证是必不可少的环节,可以替代通知行审证。()
在对J公司2004年度会计报表进行审计时,A注册会计师负责实施函证程序。在审计过程中,A注册会计师需要考虑以下事项,请代为做出正确的专业判断。
“元四家”是指黄公望、吴镇、__________和__________。
[*]
乙公司参加一个网络项目的投标,为增加中标的可能性,乙公司决定将招标文件中的一些次要项目(约占总金额的3%)作为可选项目,没有计算到投标总价中,而是另作一张可选价格表,由招标方选择是否需要。评标时,评委未计算可选价格部分,这样乙公司因报价低而中标。洽谈合同时
下列关于CPU的叙述中,正确的是________。
Werealizedthathewasundergreat_____,sowetooknonoticeofhisbadtemper.
最新回复
(
0
)