首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为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
148
问题
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为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
程序员面试
相关试题推荐
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
将一整数逆序后放入一数组中(要求递归实现)
求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
将桌面背景设置为图片WindowsXP。
下列叙述正确的是______A.通过“我的电脑”图标可以浏览和使用所有的计算机资源B.“我的电脑”是一个文件夹C.“回收站”用于存放被删除的对象,置入“回收站”中的对象在关机后自动消失D.用户可以在桌面上创建文件夹或快捷方式
信息安全包括四大要素:技术、制度、流程和()。
ITSS(InformationTechnologyServiceStandards)是一套成体系和综合配套的信息技术服务标准库,包括了IT服务全生命同期阶度应遵循的标准。关于ITSS体系框架4.0的分类,正确的是()。
信息系统的生命周期可以简化为立项、开发、运维及消亡四个阶段,()属于开发阶段的工作。
病毒和木马的根本区别是______。
随机试题
出版物生产成本中的直接成本包括()等项目。
A.弥散障碍B.第一秒用力呼气率降低C.两者均有D.两者均无支气管哮喘
当设计无具体要求时,对一、二级抗震等级的框架结构,其纵向受力钢筋检测所得的强度实测值应符合“钢筋抗拉强度实测值与屈服强度实测值的比值不应大于1.25,屈服强度实测值与强度标准值的比值不应小于1.3”的规定。()
按照住房城乡建设部、财政部《关于印发的通知》(建标[2013]44号)的规定,对建筑以及材料、构件和建筑安装物进行一般鉴定、检查所发生的费用,应在()中列支。
商业银行申请开展个人理财业务,应当向中国银监会报送的材料包括()。
(2017年)增值税一般纳税企业以支付现金方式取得联营企业股权的,所支付的与该股权投资直接相关的费用应计入当期损益。()
土地增值税纳税人是法人的,当转让的房地产坐落地与其机构所在地或经营所在地一致时,在办理税务登记的原管辖税务机关申报纳税即可。()
关于“重证据,重调查研究,严禁逼供信”的政策,下列说法错误的是()。
(厦门大学2011年初试真题)根据个人所得税法的规定,下列是个人所得税纳税人的有()。
下列变量名中,合法的()。A)B)C)D)
最新回复
(
0
)