最大子段和问题的简洁描述是：对于给定序列[ x1,x2,x3...]寻找它的某个连续子段，使得其和最大。如{ -1,5,-2,1,-7,-4,2,3,-1,2 }最大子段是{ 2,3,-1,2 }其和为6。这个问题可以从枚举、分治、动态规划，贪心这几个角度来解。
（1）枚举解法思路：对于数组a[n],其连续的子段有
以a[0]开始的 , { a[0] }, { a[0],a[1] },{ a[0],a[1],a[2] }.....共n 个
以a[1]开始的, { a[1] }, { a[1],a[2] },{ a[1],a[2],a[3] }.....共n-1个
...
以a[n]开始的，{ a[n] }共1个
一共(n+1)*n/2个连续子段，使用枚举，那么应该可以使用双重循环得到一个o( n^2 )级的算法：
int MaxSum_enum(int *arr,int n)
{
int sum = 0;
for(int i=0; i<n; ++i)
{
int thisSum = 0;
for(int j=i; j<n; ++j)
{
thisSum += arr[j];
if(thisSum > sum)
{ sum = thisSum;}
}
}
return sum;
}
当然在需要的时候，也可以设置一个区间记录值，记录这个子段的开始位置和结束位置：
int MaxSum_enum(int *arr,int n,int &besti,int &bestj)
{
/*besti bestj用于记录最大字段和区间[ besti...bestj ]*/
int sum = 0;
for(int i=0; i<n; ++i)
{
int thisSum = 0;
for(int j=i;j<=n; ++j)
{
thisSum += arr[j];
if(thisSum > sum )
{
sum = thisSum;
besti = i;
bestj = j;
}
}
}
return sum;
}
（2）分治角度的思路：
分治时，将数组划分为 [ left,mid ] 和 [ mid+1,right ] 两部分，分别求左侧区间的最大子段和，以及右边区间的最大子段和。
合并时，分为3种情况，
1.左侧区间最大子段和大于右侧区间最大子段和，且两个子段不相邻，选择左侧最大子段和
2.右侧区间最大子段和大于左侧区间最大子段和，且两个子段不相邻，选择右侧最大子段和
3.左右两个最大子段相邻，合并子段，返回两者之和
可以得到一个o(n*logn)级的算法，但代码其实是不易写正确的
（3）动态规划思路：
将每一个数是否列入当前子段作为一个决策，
1.如果加上这个数后子段和仍然大于0，那么加上这个数
2.如果加上这个数后子段和小于0，那么子段清零，下一个数作为新的子段的开始
在这个过程中记录遇到的最大子段和
int MaxSum_DP(int *arr,int n)
{
int sum = 0;
int tmp = 0;
for(int i=0; i<n; ++i)
{
if(tmp > 0) {tmp += arr[i];}
else {tmp = arr[i];}
if(tmp >sum){sum = tmp ;}
}
return sum;
}
如果需要知道最大子段的位置，可以添加记录数据：
int MaxSum_DP(int *arr,int n,int &besti,int &bestj)
{
int sum = 0;
int tmp = 0;
int tmp_start = 0;
int tmp_len = 0;
for(int i=0;i<n; ++i)
{
if( tmp > 0 ) { tmp+= arr[i]; tmp_len++;}
else { tmp = arr[i]; tmp_start = i; tmp_len = 1;}
if( tmp > sum ){ sum = tmp ; besti=tmp_start; bestj=besti+tmp_len-1;}
}
return sum;
}
算法的复杂度为O(n)
（4）其实动态规划的思路也是贪心的思路，但如果用贪心思路，更加容易理解。
1.对于每一个子段，贪心地认为加下一个数之后可能更大
2.如果加下一个数没有变大，但子段和为正，贪心地认为加再下一个数之后更大
3.如果加上某个数后子段和为负，那么放弃这个子段（因为1个元素都不选，和为0也比负数大），开始一个新的子段
4.记录贪心过程中遇到的最大子段和