首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10,
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10,
admin
2014-11-15
72
问题
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
选项
答案
如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组;而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。 很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。基于这样的思路,我们可以写出如下代码。 参考代码: ///////////////////////////////////////////////////////////////////////////// // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return false ///////////////////////////////////////////////////////////////////////////// bool FindGreatestSumOfSubArray ( int *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum // the greatest sum of all sub-arrays ) { // if the input is invalid, return false if((pData == NULL) || (nLength == 0)) return false; int nCurSum = nGreatestSum = 0; for(unsigned int i = 0; i < nLength; ++i) { nCurSum += pData[i]; // if the current sum is negative, discard it if(nCurSum < 0) nCurSum = 0; // if a greater sum is found, update the greatest sum if(nCurSum > nGreatestSum) nGreatestSum = nCurSum; } // if all data are negative, find the greatest element in the array if(nGreatestSum == 0) { nGreatestSum = pData[0]; for(unsigned int i = 1; i < nLength; ++i) { if(pData[i] > nGreatestSum) nGreatestSum = pData[i]; } } return true; } 讨论:上述代码中有两点值得和大家讨论一下: ? 函数的返回值不是子数组和的最大值,而是一个判断输入是否有效的标志。如果函数返回值的是子数组和的最大值,那么当输入一个空指针是应该返回什么呢?返回0?那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢?基于这个考虑,本人认为把子数组和的最大值以引用的方式放到参数列表中,同时让函数返回一个函数是否正常执行的标志。 ? 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时,子数组和的最大值就是数组中的最大元素。
解析
转载请注明原文地址:https://kaotiyun.com/show/ODmZ777K
0
程序员面试
相关试题推荐
TruthinadvertisingisaconceptcentraltotheAmericanfreemarketeconomicsystem.Accordingtothistheory,companiesthat
输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。
在桌面上创建一个新浪新闻网页的快捷方式。
从当前界面上开始操作,把联机用户min邀请加入到对话框中,开始多用户对话。
在金山毒霸2008中,阻止下载运行.ActiveX控件。
不能显示和编辑备注内容的视图模式是()A.普通视图B.大纲视图C.幻灯片视图D.备注页视图
在PPoint中,()新幻灯片的占位符,可添加指定的对象,如图片等。A.左键单击B.右键单击C.左键双击D.右键双击
请给学生成绩表的某列“普通物理”设置一个链接其课程简介的超链接。
将E-R图转换到关系模式时,实体与联系都可以表示成______。
下列()不属于项目群的生命周期的一个阶段。
随机试题
大容量变压器效率可达()。
患者男,61岁。冠心病7年,6小时前胸骨后剧痛,为压榨性,并向左臂放射,先后含硝酸甘油2次,疼痛稍缓解,烦躁不安,出汗。查体:急性痛苦面容,体温36.5℃,血压100/70mmHg,脉率100次/分,心界不大,律齐,心音低,未闻及奔马律及杂音,双肺少许湿啰
()为其所在省级行政区域内中小微企业证券非公开发行、转让及相关活动提供基础设施与服务的场所。
根据《中华人民共和国中外合作经营企业法》的规定,1/3以上董事可以提议召开董事会临时会议。()
Therequirementsforhighschoolgraduationhavejustchangedinmycommunity.Asaresult,allstudentsmust【C1】______sixtyhou
NetCostontheRiseCompaniesarepayingupto$10.000toregisteradomainnameontheInterneteventhoughthereisno
某注册会计师协会培训部的魏老师正在准备有关审计业务档案管理的培训课件,她的助手已搜集并整理了一份相关资料存放在Word文档“PPT素材.docx”中,按下列要求帮助魏老师完成PPT课件的整合制作:将演示文稿按下列要求分为3节,分别为每节应用不同的设计主
From2007to2010,Americanhouseholdslost$11trillioninrealestate,savings,andstocks.MorethanhalfofallU.S.worker
Ascivilizationproceedsinthedirectionoftechnology,itpassesthepointofsupplyingallthebasicnecessitiesoflife-food
A、StudentsfromAmerica.B、StudentsfromEngland.C、StudentsfromAustralia.D、StudentsfromJapan.A
最新回复
(
0
)