## 题目描述 输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值,要求时间复杂度为O(n)。 例如输入的数组为`1, -2, 3, 10, -4, 7, 2, -5`,和最大的子数组为`3, 10, -4, 7, 2`, 因此输出为该子数组的和18。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#分析与解法)分析与解法 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#解法一)解法一 求一个数组的最大子数组和,我想最直观最野蛮的办法便是,三个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(n^3)。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#解法二)解法二 事实上,当我们令currSum为当前最大子数组的和,maxSum为最后要返回的最大子数组的和,当我们往后扫描时, * 对第j+1个元素有两种选择:要么放入前面找到的子数组,要么做为新子数组的第一个元素; * 如果currSum加上当前元素a[j]后不小于a[j],则令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 MaxSubArray(int* a, int n) { int currSum = 0; int maxSum = a[0]; //全负情况,返回最大数 for (int j = 0; j < n; j++) { currSum = (a[j] > currSum + a[j]) ? a[j] : currSum + a[j]; maxSum = (maxSum > currSum) ? maxSum : currSum; } return maxSum; } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#问题扩展)问题扩展 1. 如果数组是二维数组,同样要你求最大子数组的和列? 2. 如果是要你求子数组的最大乘积列? 3. 如果同时要求输出子段的开始和结束列? ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#举一反三)举一反三 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](https://codility.com/cert/view/certDUMWPM-8RF86G8P9QQ6JC8X/details) 。