首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
28
问题
设有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
学硕统考专业
相关试题推荐
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
下列关于清朝军机处的叙述,不正确的是()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
首次提出“长期共存,互相监督”观念的是在文件()中。
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
近代日本被迫签订的第一个不平等条约是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
随机试题
收涩药不适宜的病证有
预收账款属于流动负债,因此,如果企业不单设预收账款,可以将预收账款并入应付账款科目核算。()
知道自己的名字,会应答,能辨别自己和他人的东西是属于加德纳的多元智能理论中的()。
我国政府提出:“十二五”期间,要加强畜禽粪污、秸秆、农膜等资源化利用和农业面源污染治理,力争到2020年实现化肥和农药使用量零增长,提高农产品质量,这一要求有利于()。
下列关于解决法律冲突一般原则的表述,能够成立的是()。
民主革命的遗留任务是
中国的人口发展形势非常严峻,为此国家统计局每10年进行一次全国人口普查,以掌握全国人口的增长速度及规模。按照下列要求完成对第五次、第六次人口普查数据的统计分析:新建一个空白Excel文档,将工作表sheet1更名为“第五次普查数据”,将sheet2更名
Openaccountisanarrangementbetweenthesellerwherebythegoodsaremanufacturedanddeliveredbeforepaymentisrequired.O
Cryingishardlyanactivityencouragedbysociety.Tears,betheyofsorrow,anger,orjoy,typicallymakeAmericansfeeluncom
AreTeenagersReallyCarelessAboutOnlinePrivacy?[A]Theyshare,like,everything.Howtheyfeelaboutasong,theirmathsho
最新回复
(
0
)