首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为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
140
问题
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为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
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
概述反射和序列化
设置发送邮件服务器的帐户名bob1和密码20022002。
在邮件中设置图片背景。
Dreamweaver的视图(View)菜单中,Grid→settings表示______。A.选择计量系统来设定标尺单位B.显示一个应用当前设置的背景网格C.使插入对象与最近的对齐设置对齐D.进行网格设置
数据库系统的三级模式分别为()模式、内部级模式与外部级模式。
从目前技术来看,下列打印机中打印速度最快的是________。
信息系统的生命周期可以简化为立项、开发、运维及消亡四个阶段,()属于开发阶段的工作。
随机试题
股票市场投资的特点有()
腹主动脉瘤的常见病因是_______。
患者女,52岁,右侧进行性鼻塞,涕血3个月余,鼻腔检查见右侧鼻腔暗红色新生物,质较硬,触之出血不多,似来自鼻顶部,下部达右下鼻甲上缘。若CT扫描显示,肿瘤主要位于鼻腔内,筛板局部破坏,颅内未见肿瘤,该患者较好的治疗方法应是
下面所列工程建设定额中,属于按定额编制程序和用途分类的是()。
自然人可根据需要申请开立个人银行结算账户,也可以在已开立的储蓄账户中选择并向开户银行申请确认为个人银行结算账户。()
在商业银行贷前调查中,贷款合法合规性调查主要包括()。[2016年6月真题]
下列哪一项不是“字体”对话框中的“字符间距”选项卡中的选项?()
下列各句中,语义明确、没有歧义的一句是:
设A和B都是m×n实矩阵,满足r(A+B)=n,证明ATA+BTB正定.
程序测试分为静态分析和动态测试。其中【】是指不执行程序,而只是对程序文本进行检查,通过阅读和讨论,分析和发现程序中的错误。
最新回复
(
0
)