【问题描述】给定一个有n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。
例如：
序列（-2，11，-4，13，-5，-2）的最大子序列和为20
序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）
的最大子序列和为16。
规定一个序列最大子段和至少是0，如果小于0，其结果为0。
蛮力法
穷举所有连续子序列来得到。
设含有n个整数的序列a[0…n-1]，穷举所有的连续子序列a[i…j]，求出它的所有元素之和thisSum，并通过比较将最大值存放在maxSum中，最后返回maxSum。

long maxSubSum1(int a[],int n)
{       int i,j,k;long maxSum=a[0],thisSum; for (i=0;i<n;i++)     //两重循环穷举所有的连续子序列{  for (j=i;j<n;j++){   thisSum=0;for (k=i;k<=j;k++)thisSum+=a[k];if (thisSum>maxSum)  //通过比较求最大连续子序列之和maxSum=thisSum;}}return maxSum;
}

改进的蛮力法

long maxSubSum2(int a[],int n)
{      int i,j;long maxSum=a[0],thisSum;for (i=0;i<n;i++)                 // i是子列左端位置{     thisSum=0;                // thisSum是从a[i]到a[j]的子列和for (j=i;j<n;j++)          // j是子列右端位置{      thisSum+=a[j];if (thisSum>maxSum)maxSum=thisSum;}}return maxSum;
}

分治法

long maxSubSum3(int a[]，int left，int right) 
//求a[left..right]序列中最大子段和
{  int i，j;long maxLeftSum，maxRightSum;long maxLeftBorderSum，leftBorderSum;long maxRightBorderSum，rightBorderSum;if (left==right)  //子序列只有一个元素时{　　if (a[left]>0)  //该元素大于0时返回它return a[left];else   //该元素小于或等于0时返回0return 0; } int mid=(left+right)/2;   //求中间位置maxLeftSum=maxSubSum3(a，left，mid); //求左边maxRightSum=maxSubSum3(a，mid+1，right); //求右边maxLeftBorderSum=0，leftBorderSum=0;for (i=mid;i>=left;i--)　   //求出以左边加上a[mid]元素{  leftBorderSum+=a[i];　   //构成的序列的最大和if (leftBorderSum>maxLeftBorderSum)maxLeftBorderSum=leftBorderSum;}maxRightBorderSum=0，rightBorderSum=0;for (j=mid+1;j<=right;j++)  //求出a[mid]右边元素{  rightBorderSum+=a[j];    //构成的序列的最大和if (rightBorderSum>maxRightBorderSum)maxRightBorderSum=rightBorderSum;}return max3(maxLeftSum，maxRightSum，maxLeftBorderSum+maxRightBorderSum); 
} 

最优算法(就遍历一次)
从头开始扫描数组a，用sum（初值为0）记录当前子序列之和，用max（初值为0）记录最大连续子序列和。
如果扫描中遇到负数，当前子序列和sum将会减小，若sum为负数，表明前面已经扫描的那个子序列可以抛弃了，则放弃这个子序列，重新开始下一个子序列的分析，并置sum为0。
若这个子序列和sum不断增加，那么最大子序列和max也不断增加。

int maxSubSum4(int a[],int n)
{　 int i,max=0,sum=0;for (i=0;i<n;i++){  sum+=a[i];//向右累加if (sum<0) //若当前子序列和为负数，重新开始下一子序列sum=0;if (sum>max)//发现更大和则更新当前结果max=sum;}return max;
}

类似动态规划