最大连续子序列和算法：从结果反推，找出前后依赖的相关性，去相关和冗余，来降低复杂度，复杂度为O(n), 与Sunday字符串匹配算法有点类似。
序列: a[i], (i =0,...n-1)
假如最大连续子序列和是a[k]到a[m-1]（m-1> k）, 那么a[k]到a[m-1]一定是a[0]到a[m-1]中最大连续子序列和。
subSum[i-1]代表以a[i-1]为结尾的最大连续子序列和，那么
当subSum[i-1]>0时，以a[i]为结尾的最大连续子序列和为subSum[i]=subSum[i-1]+a[i];
否则，subSum[i-1]不会对后面的a[i]做增加的贡献，直接跳过subSum[i-1]，重新开始计算新序列和，subSum[i]=a[i];
每次不断保存最大连续子序列和。
C语言实现：
#include <stdio.h>
int maxSubSum(int iArr[], int iNum)
{
int i, iMaxSum = 0, iMaxSubSum = 0;
if (iNum < 1)
return 0;
else if (iNum == 1)
return iArr[0];
iMaxSubSum = iArr[0];
iMaxSum = iArr[0];
for (i = 1; i < iNum; ++i)
{
iMaxSubSum += iArr[i] ;
if(iMaxSubSum > 0)
{
if(iMaxSubSum > iMaxSum)
iMaxSum = iMaxSubSum;
}
else
{
iMaxSubSum = 0;
}
}
return iMaxSum;
}
int main(void)
{
int iArr[] = {-2, 1,-3, 4, -1, 2, 1,-5, 4, 1, -3, 4, -3, 4};
int iArrLen = sizeof(iArr)/sizeof(iArr[0]);
printf("maxSubSum = %d\n", maxSubSum(iArr, iArrLen));
return 0;
}
