最大子列和问题（Java语言实现）
一、问题描述：给定N个整数的序列{ A 1 , A 2 , . . . , A n } ，求函数
的最大值，即求A i 到A j 连续的一段子列和最大的值。例如：某序列为{-1，-2，5，6，-11，8}，则其最大子列和为11.
二、问题分析：：一个整数序列中，可以产生出无数个子列，每个子列的和一般不相同，在此我们要求最大的子列，显然负数范围的子列和我们就不会考虑在内，因此如果所得结果小于0的数，则返回0做为结束
三、Java语言实现：
1.算法1： 暴力求解法，使用三重循环来求解，数据量小的时候没有问题，但是一旦数据量大，运行时间会很长，因为其时间复杂度为：T(n)=O(n 3 ) ,这是非常之恐怖的！以下是实现代码，数据量大的时候不推荐使用
import java.util.Scanner; //三重循环方式 public class MaxSubseqSum1 { public static void main(String[] args){ System.out.println("请输入整数列的大小:"); Scanner input=new Scanner(System.in); int N=input.nextInt(); int [] A=new int[N]; System.out.println("请输入整数列元素："); for (int i = 0; i < N; i++) { A[i]=input.nextInt(); } System.out.println("整数列为:"); for (int i = 0; i < N; i++) { System.out.print(" "+A[i]); } System.out.println(); System.out.println("最大子列和为："+MaxSubseqSum1.FindMaxSubseqSum1(A,N)); } public static int FindMaxSubseqSum1(int [] A,int N ) { int MaxSum=A[0]; for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { int ThisSum = 0; for (int k = i; k < j; k++) { ThisSum += A[k]; } if (ThisSum > MaxSum) { MaxSum = ThisSum; } } } return MaxSum; } }
2.算法2： 改进的暴力求解法。思想：对于求和的问题，例如要求某数列的前n项和，我们可以采用前k项和 = 前k-1项和+第k项的方法来求解。于是可以将算法1的第三层循环进行改进，代码如下：
import java.util.Scanner; public class MaxSubseqSum2 { public static void main(String[] args){ System.out.println("请输入整数列的大小:"); Scanner input=new Scanner(System.in); int N=input.nextInt(); int [] A=new int[N]; System.out.println("请输入整数列元素："); for (int i = 0; i < N; i++) { A[i]=input.nextInt(); } System.out.println("整数列为:"); for (int i = 0; i < N; i++) { System.out.print(" "+A[i]); } System.out.println(); System.out.println("最大子列和为："+MaxSubseqSum2.FindMaxSubseqSum2(A)); } public static int FindMaxSubseqSum2(int [] A){ int MaxSum=A[0]; int ThisSum; for (int i = 0; i < A.length; i++) { ThisSum=0; for (int j = i; j < A.length; j++) { ThisSum+=A[j]; //改进 if (ThisSum>MaxSum){ MaxSum=ThisSum; } } } return MaxSum; } }
但是，这个算法还是使用了二重循环，数据量小的时候没有问题，但是一旦数据量大，运行时间会很长，因为其时间复杂度为：T(n)=O(n 2） 。算法2已经成功地将算法1的时间复杂度降了1阶，那我们还能不能继续将算法2的复杂度降低呢？显示是可以的！一名优秀的程序员，在得到时间复杂度为T(n)=O(n 2 )的算法之后，总是希望将时间复杂度降到T(n)=O(n l o g n )！
3.算法3： 分而治之
步骤：
1.将序列从中分为左右两个子列
2.递归求得两个子列的最大和
3.从子列的中分点分头向左右两边扫描，找出跨越分界线的最大子列和
4.输出这三个最大子列和中最大的一个
我也是第一次接触分治算法，理解还不是很透彻，后期再慢慢补吧，贴上代码：
import java.util.Scanner; public class MaxSubseqSum3 { public static void main(String[] args){ System.out.println("请输入整数列的大小:"); Scanner input=new Scanner(System.in); int N=input.nextInt(); int [] A=new int[N]; System.out.println("请输入整数列元素："); for (int i = 0; i < N; i++) { A[i]=input.nextInt(); } System.out.println("整数列为:"); for (int i = 0; i < N; i++) { System.out.print(" "+A[i]); } System.out.println(); System.out.println("最大子列和为："+MaxSubseqSum3.DivideAndConquer(A,0,A.length-1)); //left为数组起点，right为数组中点. } public static int DivideAndConquer(int [] A,int left,int right){ int MaxLeftSum,MaxRightSum;//存放左、右子列的最大子列和 int MaxLeftBorderSum,MaxRightBorderSum;//存放跨分界线的左、右子列的最大子列和 int leftBorderSum,rightBorderSum;//存放放跨分界线的左、右子列的子列和 int center;//存放分点的下标 //终止条件，子列只有一个数字 if(left==right){ if (A[left]>0){ return A[left]; } else return 0; } //分的过程 center=(left+right)/2; MaxLeftSum=DivideAndConquer(A,left,center);//递归求左子列和 MaxRightSum=DivideAndConquer(A,center+1,right);//递归求右子列和 //求跨分界的最大子列和 MaxLeftBorderSum=0; leftBorderSum=0; for (int j = center; j > left; j--) { leftBorderSum+=A[j]; if (leftBorderSum>MaxLeftBorderSum){ MaxLeftBorderSum=leftBorderSum; } }//左边扫描结果 MaxRightBorderSum=0; rightBorderSum=0; for (int j = (center+1); j < right; j++) { rightBorderSum+=A[j]; if(rightBorderSum>MaxRightBorderSum){ MaxRightBorderSum=rightBorderSum; } }//右边扫描结果 return MaxSubseqSum3.FindMax(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum); } public static int FindMax(int a,int b,int c){ return (a>b)?((a>c)?a:c):((b>c)?b:c); } }
分而治之算法的时间复杂度是T(n)=O(n l o g n nlognnlogn)，已经是一个比较好的算法了，还有一个时间复杂度更低的算法
4.算法4：在线处理算法 思想：每扫描到一个元素，就求出和ThisSum，然后进行判断，如果ThisSum大于MaxSum，就更新MaxSum=ThisSum；如果ThisSum小于0，就直接令ThisSum=0；重复上述步骤，直到扫描完数组的所有元素，返回MaxSum。以下是代码实现：
import java.util.Scanner; public class MaxSubseqSum4 { public static void main(String [] args){ System.out.println("请输入整数列的大小:"); Scanner input=new Scanner(System.in); int N=input.nextInt(); int [] A=new int[N]; System.out.println("请输入整数列元素："); for (int i = 0; i < N; i++) { A[i]=input.nextInt(); } System.out.println("整数列为:"); for (int i = 0; i < N; i++) { System.out.print(" "+A[i]); } System.out.println(); System.out.println("最大子列和为："+MaxSubseqSum4.OnlineProcess(A)); } public static int OnlineProcess(int [] A){ int ThisSum=0,MaxSum=A[0]; for (int i = 0; i < A.length; i++) { ThisSum+=A[i]; if (ThisSum>MaxSum){ MaxSum=ThisSum; } else if (ThisSum<0){ ThisSum = 0; } } return MaxSum; } }
时间复杂度仅为T(n)=O(n)，所以这个算法以及非常快了，但有优点就有缺点，缺点就是它容易出错。
五、总结
还有最后6天就要到大三了，从昨天才开始系统的学习数据结构和算法，希望自己能够坚持下去，在学习Java开发的内容时也不要放弃了数据结构和算法的学习。我是先跟着慕课浙大数据结构来学习的，计划每天学习一节内容，并实现上面的算法。加油！
