首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
40
问题
设有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
学硕统考专业
相关试题推荐
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
1962年初,中共召开了中央工作会议,即“七千人大会”,其议题主要是()。
提出电磁感应定律的是物理学家()。
规定了电流、电动势、电阻等概念的物理学家是()。
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
论述公元前6世纪至公元1世纪佛教的形成与传播。
20世纪50年代到70年代初,西欧国家通过有效的社会经济政策,维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革,稳定社会
近代日本被迫签订的第一个不平等条约是()。
随机试题
胃痛常伴有的症状是
教师在教育教学活动中居于主导地位的基本权利是()
患者,男,5岁,左脸靠耳部位大片红色皮疹,瘙痒,抓破后渗出流水,病势缠绵,2年反复发作,缠绵不愈,苔薄白,脉浮数,治疗应选用
关于病人的道德权利,下述提法中正确的是
药品经营企业变更《药品经营许可证》的登记事项的,应在工商行政管理部门核准变更后几日内,向原发证机关申请《药品经营许可证》变更登记()
城市规划表明政府对特定地区的建设和发展在未来时段所要采取的行动和鼓励社会团体与公众开发建设的导向。()
下列可以成为“本年利润”账户对应账户的有()账户。
以地区为主要特征来组织销售物流,整个销售物流的各环节按不同的地区分别由各个不同的职能部门来共同完成的企业销售物流组织结构形式是()。
人体缺少()元素会造成甲状腺肿大(俗称大脖子病)。
()。
最新回复
(
0
)