最大子列和问题（Java语言实现）

痛定思痛。 2024-04-17 05:40 52阅读 0赞

## 最大子列和问题（Java语言实现） ##

**一、问题描述**：给定N个整数的序列 \{ A 1 , A 2 , . . . , A n \} \\left \\\{ A\_\{1\}, A\_\{2\},..., A\_\{n\} \\right \\\} \{ A1,A2,...,An\}，求函数 f ( i , j ) = m a x ( 0 , ∑ k = i j A k ) f\\left ( i,j\\right )= max(0,\\sum\_\{k=i\}^\{j\}A\_\{k\}) f(i,j)=max(0,∑k=ijAk)的最大值，即求 A i A\_\{i\} Ai到 A j A\_\{j\} Aj连续的一段子列和最大的值。例如：某序列为\{-1，-2，5，6，-11，8\}，则其最大子列和为11.  
**二、问题分析：**：一个整数序列中，可以产生出无数个子列，每个子列的和一般不相同，在此我们要求最大的子列，显然负数范围的子列和我们就不会考虑在内，因此如果所得结果小于0的数，则返回0做为结束  
**三、Java语言实现：**  
**1.算法1：** 暴力求解法，使用三重循环来求解，数据量小的时候没有问题，但是一旦数据量大，运行时间会很长，因为其时间复杂度为：T(n)=O( n 3 n^\{3\} n3) ,这是非常之恐怖的！以下是实现代码，数据量大的时候不推荐使用

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 n^\{2\} n2) 。算法2已经成功地将算法1的时间复杂度降了1阶，那我们还能不能继续将算法2的复杂度降低呢？显示是可以的！一名优秀的程序员，在得到时间复杂度为T(n)=O( n 2 n^\{2\} n2)的算法之后，总是希望将时间复杂度降到T(n)=O( n l o g n nlogn nlogn)！  
**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 nlogn nlogn)，已经是一个比较好的算法了，还有一个时间复杂度更低的算法  
**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开发的内容时也不要放弃了数据结构和算法的学习。我是先跟着慕课浙大数据结构来学习的，计划每天学习一节内容，并实现上面的算法。加油！