题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
分析:本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题,在2006年里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传,本题也顺利成为2006年程序员面试题中经典中的经典。
如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组;而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。基于这样的思路,我们可以写出如下代码。
/**
* @author jefferent@tom.com
*
* Time: 2011-7-20 下午04:13:38
*/
public int findSubArray(List<Integer> list){
int currentSum = 0; //记录当前累加和
int greatestSum = 0; //记录最大和
int maxValue = list.get(0); //记录最大值,应对输入全部为负数的情况
for(Integer item : list){
if(item > maxValue)
maxValue = item;
currentSum += item;
if(currentSum > greatestSum)
greatestSum = currentSum;
if(currentSum < 0)
currentSum = 0;
}
return maxValue < 0 ? maxValue : greatestSum;
}
分享到:
相关推荐
阿里巴巴技术类笔试题2_3卷(测试工程师_公共题)
华为笔试题2.
北大青鸟内部测试笔试题2北大青鸟内部测试笔试题2北大青鸟内部测试笔试题2北大青鸟内部测试笔试题2
自己总结的面试常见题\C、C++\C、C++笔试题笔试题2
算法相关笔试题2.txt;算法相关笔试题2.txt;算法相关笔试题2.txt;算法相关笔试题2.txt
北大青鸟s2升Y2官方笔试题2
2022年春招灿瑞科技的模拟IC笔试题,题量是真的大,发的word文档,做了拍照给他,太多了,我都没做完,找模拟IC工作的同学可以看看。
奇虎360 2018校园招聘技术笔试题2.docx奇虎360 2018校园招聘技术笔试题2.docx奇虎360 2018校园招聘技术笔试题2.docx奇虎360 2018校园招聘技术笔试题2.docx奇虎360 2018校园招聘技术笔试题2.docx奇虎360 2018校园招聘...
腾讯笔试题2.doc
Oracle笔试题Oracle笔试题Oracle笔试题Oracle笔试题Oracle笔试题
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
笔试题2.docx 笔试题3.docx 笔试题4_boss直聘.docx 笔试题5_面试题4的实现思路.docx 笔试题6.jpg 面试总结 面试题1.doc 面试题2.doc 面试题3.doc 面试题7+面试题8+面试题9_北京广视通达数字网络科技有限公司 中企...
java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 ...
大连华信去年的笔试题,可以给各位即将工作的同学一些参考
用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题
c笔试题c笔试题c笔试题c笔试题c笔试题c笔试题
嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集...
java 笔试题 j2ee笔试题 java笔试题 j2ee 笔试题
C#笔试题大全C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.,让你...
一、选择与填空: 1. 一块3mm厚的玻璃板折射为1.50,被置于波长为600nm(在真空中)的点光源和屏幕之间,从光源到屏幕的距离是3cm,则在光源和屏幕之间的波列数为 。