个有N个元素的整型数组arr，有正有负，数组中连续一个或多个元素组成一个子数组，这个数组当然有很多子数组，求子数组之和的最大值。例如：[0，-2，3，5，-1，2]应返回9，[-9，-2，-3，-5，-3]应返回-2。

网上有称之为最大子序列和，亦有称连续子数组最大和。个人觉得叫最大子序列和不太妥，数学上讲，子序列不一定要求连续，而这里我们的题目必然要求是连续的，如果不连续而求子序列最大和很显然就无意义了，这也是为啥又称连续子数组最大和。不过，莫要在意细节。

基本思路

想最最直观也是最野蛮的办法便是，三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。
记Sum[i, …, j]为数组A中第i个元素到第j个元素的和（其中0 <= i <= j < n>

/* 最大子数组和 设数组长度不超过30*/#define INF 1000/* 基本思路 */int Maxsum_base(int * arr, int size){int maxSum = -INF;for(int i = 0; i < size; ++i) /*for each i, got a sum[i,j]*/{int sum = 0;for(int j = i; j < size; ++j){sum += arr[j];if(sum > maxSum){maxSum = sum;}}}return maxSum;}

==================================

DP方案

考虑DP求解。这个问题可以继续像LCS、LIS一样，“从后向前”分析。我们考虑最后一个元素arr[n-1]与最大子数组的关系，有如下三种情况：

1. arr[n-1]单独构成最大子数组

2. 最大子数组以arr[n-1]结尾

3. 最大子数组跟arr[n-1]没关系，最大子数组在arr[0-n-2]范围内，转为考虑元素arr[n-2]

从上面我们可以看出，问题分解成了三个子问题，最大子数组就是这三个子问题的最大值，现假设：

1. 以arr[n-1]为结尾的最大子数组和为End[n-1]

2. 在[0-n-1]范围内的最大子数组和为All[n-1]

如果最大子数组跟最后一个元素无关，即最大和为All[n-2]（存在范围为[0-n-2]），则解All[n-1]为三种情况的最大值，即All[n-1] = max{ arr[n-1]，End[n-1]，All[n-2] }。从后向前考虑，初始化的情况分别为arr[0]，以arr[0]结尾，即End[0] = arr[0]，最大和范围在[0,0]之内，即All[0]=arr[0]。根据上面分析，给出状态方程：

All[i] = max{ arr[i]，End[i-1]+arr[i]，All[i-1] }

/* DP base version*/#define max(a,b) ( a > b ? a : b)int Maxsum_dp(int * arr, int size){int End[30] = {-INF};int All[30] = {-INF};End[0] = All[0] = arr[0];for(int i = 1; i < size; ++i){End[i] = max(End[i-1]+arr[i],arr[i]);All[i] = max(End[i],All[i-1]);}return All[size-1];}

上述代码在空间上是可以优化为O(1)的，这里就不说了，详参考《编程之美》2.14。

下面说一下由DP而导出的另一种O(N)的实现方式，该方法直观明了，个人比较喜欢，所以后续问题的求解也是基于这种实现方式来的。

仔细看上面DP方案的代码，End[i] = max{arr[i]，End[i-1]+arr[i]}，如果End[i-1]<0 End[i]=arr[i]， style="box-sizing: border-box; outline: 0px; margin: 0px; padding: 0px; overflow-wrap: break-word; text-decoration-line: underline;">什么意思？End[i]表示以i元素为结尾的子数组和，如果某一位置使得它小于0了，那么就自当前的arr[i]从新开始，且End[i]最初是从arr[0]开始累加的，所以这可以启示我们：我们只需从头遍历数组元素，并累加求和，如果和小于0了就自当前元素从新开始，否则就一直累加，取其中的最大值便求得解。

到这里其实就可以了，在《编程之美》中，作者故意没有按照这种推导来实现（我猜的），而是在End[i-1]<0 End[i]=0，从而留出了一个问题（元素全是负数怎么办），其实如果按照上面的推导直接实现的话，就不存在这个问题了。基于上面的推导，代码如下：>

/* DP ultimate version */int Maxsum_ultimate(int * arr, int size){int maxSum = -INF;int sum = 0;for(int i = 0; i < size; ++i){if(sum < 0){sum = arr[i];}else{sum += arr[i];}if(sum > maxSum){maxSum = sum;}}return maxSum;}

其实上面的方法虽说是从DP推导出来的，但是写完发现也是很直观的方法，求最大和，那就一直累加呗，只要大于0，就说明当前的“和”可以继续增大，如果小于0了，说明“之前的最大和”已经不可能继续增大了，就从新开始，如此这样。

==================================

返回最大子数组始末位置

这个问题是《编程之美》2.14的扩展问题，返回始末位置还是比较容易的，我们知道，每当当前子数组和的小于0时，便是新一轮子数组的开始，每当更新最大和时，便对应可能的结束下标，这个时候，只要顺便用本轮的起始和结束位置更新始末位置就可以，程序结束，最大子数组和以及其始末位置便一起被记录下来了，代码如下：

/* 最大子数组 返回起始位置 */void Maxsum_location(int * arr, int size, int & start, int & end){int maxSum = -INF;int sum = 0;int curstart = start = 0;  /* curstart记录每次当前起始位置 */for(int i = 0; i < size; ++i){if(sum < 0){sum = arr[i];curstart = i;     /* 记录当前的起始位置 */}else{sum += arr[i];}if(sum > maxSum){maxSum = sum;start = curstart; /* 记录并更新最大子数组起始位置 */end = i;}}}

==================================

数组首尾相连【《编程之美》解法错误分析】

这个也是2.14的扩展问题，如果数组arr[0],…,arr[n-1]首尾相邻，也就是允许找到一段数字arr[i],…,arr[n-1],arr[0],…,a[j]，使其和最大，该如何？

编程之美解法：这个问题的解可以分为两种情况：

1）   解没有跨越arr[n-1]到arr[0] （原问题）

2）  解跨越arr[n-1]到arr[0]

对于第二种情况，只要找到从arr[0]开始和最大的一段（arr[0],…,arr[j]）以及以arr[n-1]结尾的和最大的一段（arr[i],…,arr[n-1]）【Error 1】,那么第二种情况下和的最大值就为sum=arr[i]+…+arr[n-1]+arr[0]+…arr[j]。如果i<=j，则sum=arr[0]+…arr[n-1]，【Error 2】否则sum=arr[0]+…+arr[j]+arr[i]+…arr[n-1]。就是这两个地方，当时觉得有问题。

1）先说Error 1：这里分析的出发点就是错误的，因为“跨越边界的子数组最大和与它两端子数组和是否是最大无关”，前者并非后者的充分条件，这个没有直接的理论证明，举个例子，数组[1，-2，3，5，-1，2]最大子数组和为跨界子数组[1，|  3，5，-1，2]，但是[1]并非是以arr[0]开始的最大和；反过来，两端子数组和最大，这个涉及Error 2，如下

2）Error 2：反过来，两端子数组和最大（when i<=j），这个情况复杂多了，远远不是上面所说的那么简单sum= arr[0]+…arr[n-1]，例如数组[8，-10，60，3，-1，-6]，以arr[0]开始的最大子数组为[8，-10，60，3] ，以arr[n-1]为结尾的最大子数组为[60，3，-1，-6]，且i<=j，但是整体的最大子数组却不是arr[0]-arr[n-1]，而是跨界子数组[8 | 60，3，-1，-6]。

综上，这个问题不能这样思考，这也给我一个启发：一者看书要试着带有批判性的态度去看；二者别人说的不一定对，或许顺着他的思路觉得有道理，但一定要去亲自实现，实践见真知。

那么怎么做呢？

根据上面两个所举的测试用例，可以发现[1，-2，3，5，-1，2]中最大子数组去掉的是-2，而[8，-10，60，3，-1，-6]中最大子数组排除的是-10，这两个有什么特点？没错，这两个数都是两个数组中“最小”的，所以，我们找最大子数组的对偶问题——最小子数组，有了最小子数组的值，总值减去它不就可以了么？但是我又想，这个对偶问题只能处理这种跨界的特殊情况吗？答案是肯定的，如果最大子数组跨界，那么剩余的中间那段和就一定是最小的，而且和必然是负的；相反，如果最大子数组不跨界，那么总值减去最小子数组的值就不一定是最大子数组和了，例如上面我们的例子[8，-10，60，3，-1，-6]，最大子数组为[8 | 60，3，-1，-6]，而最小子数组和为[-10]，显然不能用总值减去最小值。故，在允许数组跨界（首尾相邻）时，最大子数组的和为

MaxSubSum=Max{ 不跨界的最大子数组和；数组所有元素总值-最小子数组和 }

/* 如数组首尾相邻 */int Maxsum_endtoend(int * arr, int size){int maxSum_notadj = Maxsum_ultimate(arr,size); /* 不跨界的最大子数组和 */if(maxSum_notadj < 0){return maxSum_notadj;                      /* 全是负数 */}int maxSum_adj = -INF;                         /* 跨界的最大子数组和 */int totalsum = 0;int minsum = INF;int tmpmin = 0;for(int i = 0; i < size; ++i)     /* 最小子数组和 道理跟最大是一样的 */{if(tmpmin > 0){tmpmin = arr[i];}else{tmpmin += arr[i];}if(tmpmin < minsum){minsum = tmpmin;}totalsum += arr[i];}maxSum_adj = totalsum - minsum;return maxSum_notadj > maxSum_adj ? maxSum_notadj : maxSum_adj;}

给出测试用例程序：

void main(){/* 测试用例 *///int arr[] = {8,-10,3,60,-1,-6};int arr[] = {1,-2,3,5,-1,2};int arr2[] = {-9,-2,-3,-5,-4,-6};int len = sizeof arr / sizeof(int);int len2 = sizeof arr2 / sizeof(int);/* 测试三种实现 */printf("%d %d\n",Maxsum_base(arr,len),Maxsum_base(arr2,len2));printf("%d %d\n",Maxsum_dp(arr,len),Maxsum_dp(arr2,len2));printf("%d %d\n",Maxsum_ultimate(arr,len),Maxsum_ultimate(arr2,len2));/* 返回起始位置 */int start = -1;int end = -1;Maxsum_location(arr,len,start,end);printf("start：%d end：%d\n", start, end);Maxsum_location(arr2,len2,start,end);printf("start：%d end：%d\n", start, end);/* 允许数组首尾相连 */printf("%d %d\n",Maxsum_endtoend(arr,len),Maxsum_endtoend(arr2,len2));}

思考：有木有方法可以直接处理允许数组首尾相邻的情况，即不用先求原问题的最大子数组，然后再使用对偶问题求一个值取二者最大，而是一步到位？有木有？求之。

==================================

类似问题

类似问题看了

• 子数组的最大乘积-《编程之美》2.13

• 最大子矩阵-《编程之美》2.15

通过这些问题的研究，我们可以注意以下几点算法设计思想：

• 保存状态，避免重复计算：动态规划的思想

• 将信息预处理到数据结构中（类似问题中），即“部分积”、“部分和”的应用

• 扫描算法。与数组相关的问题常可以考虑“如何将arr[0,...i]的问题转为求解arr[0,...i-1]的问题”