最大和子数组是数组中和最大的子数组，又名最大和子序列。子数组是数组中连续的n个元素，比如a2,a3,a4就是一个长度为3的子数组。顾名思义求最大和子数组就是要求取和最大的子数组。
n个元素的数组包含n个长度为1的子数组：{a0}，{a1}，…{an-1}；
n个元素的数组包含n-1个长度为2的子数组：{a0,a1}，{a1,a2}，{an-2,an-1}；
………………………………………………………………………………………………
n个元素的数组包含1个长度为n的子数组：{a0,a1,…,an-1}；
所以，一个长度为n的数组包含的子数组个数为n+(n-1)+…+1=n*(n-1)/2。
第一反应就是蛮力法，穷举数组所有子数组的和并求出和的最大值。这种方法简单直观容易想到，具体又有几种不同的思路。第一种方法是先求出所有长度为1的子数组的和，再求长度为2的子数组的和，以此类推，直到求出所有长度为n的子数组的和，并在求子数组和的过程中记录和的最大值。伪代码如下：
maxSum=arr[0];//maxSum记录最大子数组和
for（i=1,i<=n;i++){//子数组长度
for(j=0;j<n;j++){//子数组开始的位置（数组下标）
sum=0;//sum记录当前子数组和
for(k=j;k<n&&k<j+i;k++){//求和
sum+=arr[k];
}
if(sum>maxSum) maxSum=sum;
}
}
第二种方法是先求所有以a[0]开始的子数组的和，再求所有以a[1]开始的子数组的和，以此类推，直到最后求出所有以a[n-1]开始的子数组的和，并在求子数组和的过程中记录和的最大值。伪代码如下：
int maxSubArraySum(int *arr,int n){
int i,j,maxSum=arr[0],sum;
for(i=0;i<n;i++){//子数组开始位置
sum=0;
for(j=i;j<n;j++){//以arr[i]开始的不同长度的子数组的和，求和是一个递进过程
sum+=arr[j];
if(sum>maxSum) maxSum=sum;
}
}
return maxSum;
}
蛮力法虽然可以求得问题的解，但蛮力法通常不是我们所希望的，其时间复杂度大。我们希望找到一 种更有效的方法来解决该问题，所以需要思考问题具有的特征，拿到问题就开始写代码是最忌讳的，代码前需要三思。最大和子数组一定以数组中的某个元素a[i](0<=i<n)结束，那么我们可以先分别求出以每个元素结尾的子数组的最大和，其中的最大值就是所求的最大子数组和。后一个元素的求和需要用到前一个元素的结果，递推公式为maxSumEnd[i]=max{maxSumEnd[i-1]+a[i]，a[i]}，代码如下：
int maxSumArraySumD(int *arr,int n){
int i,maxSum=arr[0];
int *maxSumEnd;
maxSumEnd=(int*)malloc(sizeof(int)*n);
maxSumEnd[0]=arr[0];
for(i=1;i<n;i++){
if(maxSumEnd[i-1]+arr[i]>arr[i])
maxSumEnd[i]=maxSumEnd[i-1]+arr[i];
else
maxSumEnd[i]=arr[i];
if(maxSumEnd[i]>maxSum)
maxSum=maxSumEnd[i];
}
free(maxSumEnd);
return maxSum;
}
这道题目如果我们能联想到一些数学知识就可以得到更简洁的答案，优秀的程序猿一定具有很厚的数学基础和敏捷的数学思维，但有很厚数学基础和敏捷数学思维的人不一定就是程序猿，历史证明无数优秀的数学家都变成了经济学家，计算机这个专业学到后面也就剩英语和数学了，华尔街那帮吸血鬼个个都是数学怪才。
一个数加上一个负数和会变小，一个数加上0和保持不变，一个数只有加上一个正数和才会变大。如果最大和子数组为a[i]，a[j]，a[k]，那么一定有a[i]+a[j]>0，如果a[i]+a[j]<=0，那么最大和子数组就是a[k]。因此，我们可以从a[0]累加求和，只要累加的和大于0就继续向后累加，如果累加的和小于0，那就舍弃掉，从下一个元素从新开始累加，并在累加过程中记录和的最大值。代码如下：
int maxSubArraySum(int *arr,int n){
int i,maxSum=arr[0],sum=0;
for(i=0;i<n;i++){
sum+=arr[i];
if(sum>maxSum){ //记录最大累加和
maxSum=sum;
}
if(sum<0){//累加和小于0舍弃
sum=0;
}
}
return maxSum;
}
或许还需给出最大和子数组，那么要在求最大和子数组的过程中记录最大和子数组的起始位置。代码如下：
int maxSubArraySumPos(int *arr,int n){
int i,maxSum=arr[0],sum=0;
int start=0,end=0,s=0,e=0;
for(i=0;i<n;i++){
sum+=arr[i];
if(sum>maxSum){
maxSum=sum;
e=i;
start=s;
end=e;
}
if(sum<0){
sum=0;
s=i+1;
e=i+1;
}
}
printf("start=%d end=%d\n",start,end);
return maxSum;
}
罗马之路不顺畅，大侠们不要吝啬自己的武功秘籍，评论区为各位大侠所留。