2.4 最大连续子数组和

题目描述

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

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。

分析与解法

解法一

求一个数组的最大子数组和，我想最直观最野蛮的办法便是，三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。 令currSum[i, …, j]为数组A中第i个元素到第j个元素的和（其中0 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) 。