穷举法是最容易想出的解法，反正就是把所有能举出的子序列都算一遍和，找出最大的一个就是，复杂度O(N*N)。
对于分治法来说，“分“是比较简单的，对半分成求解左右两个序列的最大子序列，不过终止条件应该是什么呢？我的想法是到只剩一个元素的序列的话，直接返回这个元素就是了，可书上都是如果大于0，返回此元素，若小于0，则返回0，这里想不明白。最难的部分应该是“治”，要考虑跨左右两个子序列的情况。
int MaxSubSeqSum(int a[],int left,int right)
{
if(left==right)
{
return a[left];
}
int mid = (left+right)/2;
int i,lSum=0,rSum=0,tmpLMax=0,tmpRMax=0;
for(i=mid;i>=left;--i)
{
lSum+=a[i];
if(lSum>tmpLMax)
{
tmpLMax = lSum;
}
}
for(i=mid+1;i<=right;++i)
{
rSum+=a[i];
if(rSum>tmpRMax)
{
tmpRMax = rSum;
}
}
int overMax = tmpLMax+tmpRMax;
int lMax = MaxSubSeqSum(a,left,mid);
int rMax = MaxSubSeqSum(a,mid+1,right);
return max(max(overMax,lMax),rMax);
}
动态规划的方法就太巧妙了，巧就巧在它扫描时会跟踪序列上升还是下降的趋势，从而把前面不适合的部分都给抛弃了，就一路走一路抛，并且同时把合适的记忆住了。
int MaxSubSeqSum2(int a[],int len)
{
int tmpSum=0,maxSum = 0;
for(int i=0;i<len;++i)
{
tmpSum+=a[i];
if(tmpSum>maxSum)
{
maxSum = tmpSum;
}
else if(tmpSum<0)
{
tmpSum=0;
}
}
return maxSum;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/04/03/1136224.html，如需转载请自行联系原作者
