求子数组的最大和|微软经典面试题解析


---答题基础知识储备---

动态规划:基本思想与“分治”思想类似,通过将待求解的问题拆分成若干子问题(阶段),按顺序求解子阶段,前一子阶段的解,为后一子阶段的求解提供有用信息。

在求解任一子阶段问题时,列出各种可能的局部解,通过决策,保留最有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

动态规划算法与分治算法的区别:动态规划法分解后得到的子问题,往往不是相互独立的,下一阶段的解一般建立在上一阶段的解之上,进行进一步求解。

------

题目:

输入一个整型数组,数组里有正数也有负数。将数组中连续的一个或多个整数组成一个子数组,每个子数组有一个和。求所有可能组成的子数组中,和的最大值,要求时间复杂度为O(n)。

例如:输入的整型数组为1,-2,3,10,-4,7,2,-5,那么这个整型数组中,和最大的子数组为3,10,-4,7,2,因此,输出该整型数组的最大和为18。


答题分析:

这道题,如果直接通过枚举的方式来实现:一个有n个元素的数组,其连续子序列数组的最多可能有n(n+1)/2个,将全部连续子序列枚举出来的算法复杂度为O(n^2);然后,对一个长度为n的数组所有子序列数组元素求和的算法复杂度为O(n),所以通过枚举方式实现总的算法复杂度为O(n^3);不符合题目O(n)的要求。

在这里,我们可以使用动态规划的方式来实现:从左到右依次遍历数组元素,将元素递加求和,使用sum保存和值,使用max保存和的最大值,若出现sum<0,则将sum清零,重新开始递加。


解答:

代码实现:

int maxSubarray(){
    int arr[] = {1, -10, 20, 5, 7, -9, 13, -2, 30, 6, -7, 4};
    int sum=0,max=0,len=12;
    for(int i=0;i<len;i++){
        sum += arr[i];
        max = MAX(sum,max);
        if(sum<0) sum=0;
    }
    return max;
}


需要注意的是:如果求解的整型数组中全是负数值,那么求和最大值应该数组的最大值,单独考虑计算。

本文发表于2017年10月26日 15:25
阅读 2685 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

4968 1346840
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

让一个团队走向平庸的最佳方式,是让成员们持续地干那些不让他们感到自豪的事情。

最近1 2年发现成长的最好方式是研究开源的项目,自己实践。成长速度非常的快,一个好的项目需要考虑的细节很多。

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

18年元旦立下的flag要集中突击一下了.....

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.