求子数组的最大和
题目描述:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4,7, 2,因此输出为该子数组的和18。
这个问题在各大公司面试中出现频率之频繁,被人引用次数之多,非一般面试题可与之匹敌。ok,下面,咱们来一步一步分析这个题。
分析与解法
解法一
求一个数组的最大子数组和,我想最直观最野蛮的办法便是,三个for循环三层遍历,求出数组中每一个子数组的和,最终求出这些子数组的最大的一个值。令currSum[i, …, j]为数组A中第i个元素到第j个元素的和(其中0 <= i <= j < n),maxSum为最终求到的最大连续子数组的和。
且当全是负数的情况时,我们可以让程序返回0,也可以让程序返回最大的那个负数,这里,我们让程序返回最大的那个负数。
参考代码如下:
int MaxSubArray(int* A, int n)
{
int maxSum = a[0]; //全负情况,返回最大负数
int currSum = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = i; k <= j; k++)
{
currSum += A[k];
}
if (currSum > maxSum)
maxSum = currSum;
currSum = 0; //这里要记得清零,否则的话sum最终存放的是所有子数组的和。
}
}
return maxSum;
}
这个实现的复杂度是O(3)
解法二
事实上,当我们令currSum为当前最大子数组的和,maxSum为最后要返回的最大子数组的和,当我们往后扫描时,
- 对第i+1个元素有两种选择:要么放入前面找到的子数组,要么做为新子数组的第一个元素;
·如果currSum加上当前元素a[j]后currSum变大了,则令currSum加上a[j],否则currSum重新赋值,置为下一个元素,即currSum = a[j]。
- 同时,当currSum > maxSum,则更新maxSum = currSum,否则保持原值,不更新。
即:
currSum = max(a[j], currSum + a[j])
maxSum = max(maxSum, currSum)
,当输入数组是1, -2, 3, 10, -4, 7, 2, -5,那么,currSum和maxSum相应的变化为:
- currSum: 0 1 - 1 3 13 9 16 18 13
- maxSum : 0 1 1 3 13 13 16 18 18
参考代码如下:
//本段代码引自编程之美
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;
}
问题扩展
- 如果数组是二维数组,同样要你求最大子数组的和列?
- 如果是要你求子数组的最大乘积列?
- 如果同时要求输出子段的开始和结束列?
举一反三
1 给定整型数组,其中每个元素表示木板的高度,木板的宽度都相同,求这些木板拼出的最大矩形的面积。并分析时间复杂度。
此题类似leetcode里面关于连通器的题,需要明确的是高度可能为0,长度最长的矩形并不一定是最大矩形,还需要考虑高度很高,但长度较短的矩形。如[5,4,3,2,4,5,0,7,8,4,6]中最大矩形的高度是[7,8,4,6]组成的矩形,面积为16。
2、环面上的最大子矩形
《算法竞赛入门经典》 P89 页。
3、最大子矩阵和
一个M*N的矩阵,找到此矩阵的一个子矩阵,并且这个子矩阵的元素的和是最大的,输出这个最大的值。如果所有数都是负数,就输出0。例如:3*5的矩阵:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
和最大的子矩阵是:
4 5
5 3
最后输出和的最大值17。
4、允许交换两个数的位置 求最大子数组和。
来源:https://codility.com/cert/view/certDUMWPM-8RF86G8P9QQ6JC8X/details
有误欢迎指出, 分享请标明出处, 谢谢!
分享到:
相关推荐
C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程
这年头,有个示例程序是多么的重要,节省了大量时间。
很好的,大家来看看 吧.初学的菜鸟来看看 吧其实我 是菜鸟啊啊
C/C++ threadpool封装, 线程池, Linux, 多线程, pthread
此程序使用的是#define创建的函数来作为储存的不可直接用于(if)判断
c++基础c++类,类的实例,类的指针,成员函数,构造函数.,适合新手菜鸟小白看,
使用的是C++编写的智能快递柜,无前端页面,只在工作台使用
RC4加密,想用的下吧,虽然是菜鸟,但觉得自己写的这个还不错
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++...
c++ builder经典入门 对于刚接触的菜鸟来说非常有用
职场菜鸟需要注意的一些细节问题,一定会对你有所帮助!
c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮
同时标准化委员会声明就有的C++头文件将不再列于被支持的名单之中了,而旧有的C头文件为了满足“对C的兼容性”这个古老契约,仍然将继续存活下去。 但是,那些编译器厂商不可能去推翻他们客户的旧有编译器(也跟本...
c++基础知识 适合初学者 内容全面 菜鸟必看
菜鸟教程(Runoob)提供的免费网上编译器! 包含C++ C C# HTML/CSS/JavaScript PHP Python等许多语言的编译器! 还有画图 进制转换等常用工具! 还有资源共享! 欢迎来到(http://c.runoob.com)!
包含选择题,填空题以及上机操作题。比如 下述程序的输出结果是()。 int x = 10; y = x++; printf(“%d, %d”, (x++, y), y++); A、11, 10 B、11, 11 C、10, 10 D、10, 11 试卷考查应试者的c语言能力,
师兄推荐的研究生找工作前必看的书。教你如何从菜鸟进化为编程高手。
我们大学上课老师的讲课内容。。。 我们老师很牛逼,觉得清华教材讲的很深,不利于全然不会的弱弱弱菜鸟学习。。 便,自创C++教材,,,供我们学习~ *注意:要有C语言基础*
这是本人刚入职作的作业,因为刚毕业,所以写的代码基本不能看,也希望各位能点评一下,自己刚学习,哎,还有好多考虑到,希望大家可以帮我找下bug和优化下代码,谢谢了! 自己是刚毕业工作的学生,所以写得很laji...
c语言菜鸟必看代码c语言菜鸟必看c语言菜鸟必看代码代码