四种求最大子序列和的方法，效率一个比一个高。
方法二是方法一的改进
方法三是采用分治的思想，编写递归函数
方法四 最为巧妙，代码少，效率高，逻辑清晰
对原书中的代码做了一小点修改，能处理负数数组（结果为最小的负数）
附上代码
package chapter2;
import java.util.Random;
public class maxSubSum
{
/*-------------------------------方法1 --------------------------------*/
public int maxSubSum1(int[] a)//方法1
{
//最笨的方法，分别以每个元素为起点 计算每一种长度的和
int sum=a[0],sumMax=a[0];
for (int i = 0; i < a.length; i++)//每一个元素为起点
{
for (int j = i; j < a.length; j++)//每一种子序列长度
{
sum=a[i];
for(int k=i+1;k<=j;k++)//求和
sum+=a[k];
if (sumMax<sum)//比较更新Max
{
sumMax=sum;
}
}
}
return sumMax;
}
/*-------------------------------方法2 --------------------------------*/
public int maxSubSum2(int[] a)//方法二
{
//方法一的改进，通过一个for循环直接得出 某个元素为起点的所有子序列的最大和
int sum=0,sumMax;
sumMax=a[0];
for (int i = 0; i < a.length; i++)//选取每一个元素为起点
{
sum=0;
for (int j = i; j < a.length; j++)//比较每一种序列的和
{
sum+=a[j];
if (sum>sumMax)
sumMax=sum;
}
}
return sumMax;
}
/*-------------------------------方法3 --------------------------------*/
public int maxSubSum3(int[] a,int left,int right)//方法三
{
//分治策略
//每次把数组分成左右两部分，
//最大子序列和可能在三处出现，整个序列出现在左边或者右边，或者跨越中部
if (left==right) //基本情况，left=right，只有一个元素
return a[left];
int center=(left+right)/2;//递归，继续分成左右两部分，
int maxLeftSum=maxSubSum3(a, left, center);//返回左边的最大和
int maxrightSum=maxSubSum3(a, center+1, right);//返回右边的最大和
//计算从center为起点，分别向左和向右的最大序列和
//center向左的最大子序列和
int maxLeftBorderSum=a[center],leftBorderSum=a[center];
for (int i = center-1; i >= left; i--)
{
leftBorderSum+=a[i];
if (leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
}
//center向右的最大子序列和
int maxrightBorderSum=a[center+1],rightBorderSum=a[center+1];
for (int i = center+2; i <=right; i++)
{
rightBorderSum+=a[i];
if (rightBorderSum>maxrightBorderSum)
maxrightBorderSum=rightBorderSum;
}
//返回三种情况的最大值（整个在左边，整个在右边，跨区域）
int max;
max=maxLeftSum>maxrightSum? maxLeftSum:maxrightSum;
max=max>maxLeftBorderSum+maxrightBorderSum?max:maxLeftBorderSum+maxrightBorderSum;
return max;
}
/*-------------------------------方法4 --------------------------------*/
public int maxSubSum4(int[] a)//方法四
{
//效率最高，代码最简单
//思路：小于0的子序列（包括单个元素的情况）比较sumMax后直接抛弃，sum重置为0，继续累加
int sum=a[0],sumMax=a[0];
for (int i = 1; i < a.length; i++)
{
sum+=a[i];
if (sum>sumMax)
sumMax=sum;
if (sum<0)
sum=0;
}
return sumMax;
}
public static void main(String[] args)
{
int[] a=new int[1000];
for (int i = 0; i < a.length; i++)//随机数给数组赋值
{
a[i]=(int )( (0.5-Math.random())*100);
if (a[i]==0)
a[i]=-8;
}
maxSubSum test=new maxSubSum();
System.out.println(test.maxSubSum4(a));
System.out.println(test.maxSubSum3(a,0,999));
System.out.println(test.maxSubSum2(a));
System.out.println(test.maxSubSum1(a));
}
}