程序员编程艺术:第七章、求连续子数组的最大和
作者:July。
出处:http://blog.csdn.net/v_JULY_v。
前奏
- 希望更多的人能和我一样,把本狂想曲系列中的任何一道面试题当做一道简单的编程题或一个实质性的问题来看待,在阅读本狂想曲系列的过程中,希望你能尽量暂时放下所有有关面试的一切包袱,潜心攻克每一道“编程题”,在解决编程题的过程中,好好享受编程带来的无限乐趣,与思考带来的无限激情。--By @July_____。
- 原狂想曲系列已更名为:程序员编程艺术系列。原狂想曲创作组更名为编程艺术室。编程艺术室致力于以下三点工作:1、针对一个问题,不断寻找更高效的算法,并予以编程实现。2、解决实际中会碰到的应用问题,如第十章、如何给10^7个数据量的磁盘文件排序。3、经典算法的研究与实现。总体突出一点:编程,如何高效的编程解决实际问题。欢迎有志者加入。
第一节、求子数组的最大和
3.求子数组的最大和
题目描述:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
分析:这个问题在各大公司面试中出现频率之频繁,被人引用次数之多,非一般面试题可与之匹敌。单凭这点,就没有理由不入选狂想曲系列中了。此题曾作为本人之前整理的微软100题中的第3题,至今反响也很大。ok,下面,咱们来一步一步分析这个题:
1、求一个数组的最大子数组和,如此序列1, -2, 3, 10, -4, 7, 2, -5,我想最最直观也是最野蛮的办法便是,三个for循环三层遍历,求出数组中每一个子数组的和,最终求出这些子数组的最大的一个值。
记Sum[i, …, j]为数组A中第i个元素到第j个元素的和(其中0 <= i <= j < n),遍历所有可能的Sum[i, …, j],那么时间复杂度为O(N^3):
//本段代码引自编程之美
int MaxSum(int* A, int n)
{
int maximum = -INF;
int sum=0;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
for(int k = i; k <= j; k++)
{
sum += A[k];
}
if(sum > maximum)
maximum = sum;
sum=0;//这里要记得清零,否则的话sum最终存放的是所有子数组的和。也就是编程之美上所说的bug。多谢苍狼。
}
}
return maximum;
}
2、其实这个问题,在我之前上传的微软100题,答案V0.2版[第1-20题答案],便直接给出了以下O(N)的算法:
3、不少朋友看到上面的答案之后,认为上述思路2的代码,没有处理全是负数的情况,当全是负数的情况时,我们可以让程序返回0,也可以让其返回最大的那个负数,下面便是前几日重写的,修改后的处理全是负数情况(返回最大的负数)的代码:
4、DP解法的具体方程:@ flyinghearts:设sum[i] 为前i个元素中,包含第i个元素且和最大的连续子数组,result 为已找到的子数组中和最大的。对第i+1个元素有两种选择:做为新子数组的第一个元素、放入前面找到的子数组。
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
扩展:
1、如果数组是二维数组,同样要你求最大子数组的和列?
2、如果是要你求子数组的最大乘积列?
3、如果同时要求输出子段的开始和结束列?
第二节、Data structures and Algorithm analysis in C
下面给出《Data structures and Algorithm analysis in C》中4种实现。
本章完。
3.3续、求给定区间内的第K小(大)元素
第九章、闲话链表追赶问题
第十章、如何给10^7个数据量的磁盘文件排序
版权所有,本人对本blog内所有任何内容享有版权及著作权。实要转载,请以链接形式注明出处。
分享到:
相关推荐
o 2.2 寻找和为定值的两个数 o 2.3 寻找和为定值的多个数 o 2.4 最大连续子数组和 o 2.5 跳台阶 o 2.6 奇偶排序 o 2.7 荷兰国旗 o 2.8 矩阵相乘 o 2.9 完美洗牌 o 2.15 本章习题 第三章 树 o 3.0 本章导读 o 3.1 ...
July在西电的讲座,包括面试中经常考的算法、海量数据处理和机器学习
程序员编程艺术:面试和算法心得
希望更多的人能和我一样,把本狂想曲系列中的任何一道面试题当做一道简单的编程题或一个实质性的问题来看待,在阅读本狂想曲系列的过程中,希望你能尽量暂时放下所有有关面试的一切包袱,潜心攻克每一道“编程题”,...
程序员编程艺术是每一个程序员都应该具备的核心能力。本资源给我们介绍了如何提高我们的这方面的能力的方方面面的知识。值得大家收藏。
程序员编程艺术pdf可编辑,教你如何将编程作为一门艺术
本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。 特此分享,完全免费0积分...
本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。 特此分享,完全免费0积分...
程序员编程艺术第一~三十七章集锦.pdf
程序员编程艺术第一~三十七章集锦。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
编程艺术的继续创作仍需要得到广大读者的更多支持,最近,正在review和优化编程艺术系列,即在徐徐创作新的章节的同时,不断回顾已写的37章,希望能找出所有显而易见的bug,包括优化相关代码,希望有更多的朋友...
本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版
从2011年4月写下第一篇至今,编程艺术系列已经写了37章,也就是说详细阐述了37个编程问题,在创作的过程当中,得到了很多朋友的支持,特别是博客上随时都会有朋友不断留言,或提出改进建议,或show出自己的思路、...
围绕“面试”、“算法”、“编程”三个主题的程序员编程艺术系列(简称TAOPP系列),从今年4月写第一篇起,至今快有一年。近1年的创作中,写了二十七章,共计22篇文章。这是本人的第4大原创作品,不过与之前微软面试...
本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。 特此分享,完全免费0积分...
程序员编程艺术第一~二十七章集锦与总结(教你如何编程)by_July
本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。 特此分享,完全免费0积分...
程序员职业规划:让自己变得重要 程序员职业规划:让自己变得重要