PTA最大子列和问题（Java）

浙大数据结构mooc上的一个小例子，在此总结一下。

内容：PTA\最大子列和\java实现

前言：这个问题是我在学习浙大数据结构mooc上看到的，所以在此总结一下。

CSDN链接：https://blog.csdn.net/qq_42672532/article/details/102638421

PTA最大子列和问题：
>

问题描述：给定N个整数的序列{A1，A2，A3，……，An}，求解子列和中最大的值。

例如给出{-2，11，-4，13，-5，-2}这样一个序列，正确的最大子列和为20

第一种方法：三层循环
原理：就是穷举，按照顺序一个一个算，很麻烦，但是很好懂。
时间复杂度：O(n^3)

import java.util.Scanner;

//最大子列和第一种方法
public class Main {
    public static int maxSubseqSum1(int a[],int N){
        int maxSum = 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;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(maxSubseqSum1(a,N));
    }
}

结果果不其然，后面计算量大以后超时了，太暴力了。

第二种方法：减少一次循环
原理：相同的i不同的j，计算和的时候可以不从头开始加，直接按照刚才的那个加下一个数即可。
时间复杂度：O(n^2)

import java.util.Scanner;

//最大子列和第二种方法
public class Main {
    public static int maxSubseqSum1(int a[],int N){
        int maxSum = 0;
        //i是左端，j是右端
        for (int i = 0; i < N; i++) {
            int thisSum = 0;
            //对于相同的i，不同的j，下一次直接加在上一次的结果上。
            for (int j = i; j <N ; j++) {
                thisSum += a[j];
                if(thisSum>maxSum){
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(maxSubseqSum1(a,N));
    }
}

这一次结果正确了，没有超时。

测试点提示结果耗时内存
0 sample 有正负，负数开头结尾，最大和有更新答案正确 115 ms 10920 KB
1 100个随机数答案正确 146 ms 10856 KB
2 1000个随机数答案正确 199 ms 14184 KB
3 10000个随机数答案正确 360 ms 23524 KB
4 100000个随机数答案正确 5642 ms 52788 KB

第三种方法：分而治之
原理：分成左右两个部分，求两边的最大和，然后求出跨越两边的最大和，一直递归。
时间复杂度：O(NlogN)

import java.util.Scanner;

//最大子列和第三种方法
//代码是根据mooc上写出来的，有一部分稍作改动
public class Main {
    //三个数字里找最大
    public static int foundMax(int a,int b,int c){
        int max = 0;
        if(a>max){
            max = a;
        }
        if(b>max){
            max = b;
        }
        if(c>max){
            max = c;
        }
        return max;
    }
    public static int divideAndConquer(int a[],int left,int right){
        int maxSum = 0;
        //定义左边最大和，右边最大和，跨越两边扫描的左边最大和，右边最大和
        int rightMaxSum ,leftMaxSum ;
        int maxLeftBorderSum, maxRightBorderSum;
        int maxBorderSum;
        //当前左边和，当前右边和
        int leftBorderSum =0 , rightBorderSum = 0;
        //中心位置和数字
        int center, i;

        //只有一个数字的时候，最大子列和就是这个数
        // 也是递归的终止条件
        if(left==right){
            if(a[left]>0)return a[left];
            else{return 0;}
        }
        //分
        center = (right+left)/2;
        //递归得到左边最大和和右边最大和
        leftMaxSum = divideAndConquer(a,left,center);
        rightMaxSum = divideAndConquer(a,center+1,right);

        //跨中点的最大子列和
        maxLeftBorderSum = 0;
        maxRightBorderSum = 0;
        //从中点向左扫描
        for (i = center; i>=left; i--) {
            leftBorderSum += a[i];
            if(leftBorderSum>maxLeftBorderSum){
                maxLeftBorderSum = leftBorderSum;
            }
        }
        //从中点向右扫描
        for (i =center+1; i<=right ; i++) {
            rightBorderSum += a[i];
            if(rightBorderSum>maxRightBorderSum){
                maxRightBorderSum = rightBorderSum;
            }
        }
        maxBorderSum = maxLeftBorderSum+maxRightBorderSum;
        maxSum = foundMax(maxBorderSum,leftMaxSum,rightMaxSum);
        return maxSum;
    }

    public static int maxSubseqSum3(int a[],int N){
        return divideAndConquer(a,0,N-1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(maxSubseqSum3(a,N));
    }
}

结果耗时更短。

测试点提示结果耗时内存
0 sample 有正负，负数开头结尾，最大和有更新答案正确 120 ms 10832 KB
1 100个随机数答案正确 130 ms 10704 KB
2 1000个随机数答案正确 169 ms 12692 KB
3 10000个随机数答案正确 293 ms 21396 KB
4 100000个随机数答案正确 667 ms 50196 KB

相比较第二个方法，确实快了不少。

20 01-复杂度1 Java (openjdk) 667 ms 慕珩
20 01-复杂度1 Java (openjdk) 5642 ms 慕珩

第四种方法：在线处理
原理：从第一个数开始，向右累加，如果有更大的则更新当前结果，如果变成负数则舍弃前面的，从下一个开始。
（因为负数不可能使后面的子列和增加。）
时间复杂度：O(N) （应该是最快的了，因为你总要把所有的数字扫描一遍吧）

import java.util.Scanner;

//最大子列和第4种方法
//代码是根据mooc上写出来的，有一部分稍作改动
public class Main {
    public static int onlineFound(int a[],int N){
        int thisSum =0,maxSum = 0;
        for (int i = 0; i < N; i++) {
            thisSum += a[i];
            if(thisSum>maxSum){
                maxSum = thisSum;
            }
            else if(thisSum<0){
                thisSum = 0;
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(onlineFound(a,N));
    }
}

结果又比分而治之更快。

测试点提示结果耗时内存
0 sample 有正负，负数开头结尾，最大和有更新答案正确 121 ms 10952 KB
1 100个随机数答案正确 119 ms 10796 KB
2 1000个随机数答案正确 129 ms 13336 KB
3 10000个随机数答案正确 198 ms 22740 KB
4 100000个随机数答案正确 543 ms 52336 KB

2、3、4方法相比：
4 543 ms
3 667 ms
2 5642 ms

写在最后：因为不太喜欢C语言（因为指针那些的没学好= =），所以学数据结构就想尝试用java写出来，不过我猜以后考研还会再用c写（想吐）。

这个最大子列和问题虽然是对着mooc上的思路来的，但是每一步现在都很清晰明了了，自己写也可以写出来了，也算是一大突破。（捂脸，以前太懒太笨了，写不出来。）

另外，吼一嗓子：浙大的mooc课真的很不错！！！（眼神暗示）