求整数数组中最大子数组的和（1）

​
​

一、前言

活动地址：CSDN21天学习挑战赛

本系列的文章将解决求整数数组中最大子数组的和及其扩展问题
题目来源于此：现代程序设计 作业2
题目如下

绝大部分同学都已经做出来了单维数组的 求数组中最大子数组的和, 但是你不妨试一试:把你的程序编译为可执行文件, 然后执行 例如 maxsum.exe 输出就是最大子数组的和, 上面的例子就应该输出 16.
如果输入的数组很大, 并且有很多大的数字, 就会产生比较大的结果 (考虑一下数的溢出), 请保证你的程序能正常输出。
另外, 如果输入文件的参数有错误, 这个程序应该能正常退出, 并显示相应的错误信息。 任何输入错误都不能导致你的程序崩溃 (对的, TA 会模拟一些有错误的文件来检查)。

二、构思

这里的子数组指的是连续的几个数字，为了保证有序，可以采取将第一个数作为固定的数字，依次将后面的数字与第一个数相加求和

第一次：a[0] + a[1]
第二次：a[0] + a[1] + a[2]
第三次：a[0] + a[1] + a[2] + a[3]
······
第n次：a[0] + a[1] + a[2] + a[3] + ··· + a[n]
这就需要用到累加的思想，通过一次 for 循环 来完成（内循环）

当第一个数字完成以上操作以后，第二个数字也要完成如此操作

第一次：a[1] + a[2]
第二次：a[1] + a[2] + a[3]
第三次：a[1] + a[2] + a[3] + a[4]
······
第n次：a[1] + a[2] + a[3] + a[4] + ··· + a[n]
这也需要用一次for循环来完成（外循环）

由于要输出最大值，所以要将累加的和sum与最大值max比价，如果sum更大，就把此时sum的值赋值给max

此处max和sum需要初始化，于是我就把它的初始值都设为0（此处有bug）

由于要返回最大值，所以要将上述过程封装在一个带返回值的方法内，返回值为max

三、代码实现

1.初次代码

首先我测试了一个正数组，结果正确

public static void main(String[] args) {

        int[] arr = {8,2,6，2,1,56,9};
        
        System.out.println(maxSonArray(arr));
        
    }

    public static int maxSonArray(int [] a){
    
        int max = 0;
        
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i + 1; j < a.length; j++){
                sum += a[j];
                
                if(sum > max){
                    max = sum;
                }
                
            }

        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

运行结果：76

接着我测试了一个有正有负的数组，结果也正确

public static void main(String[] args) {

        int[] arr = {8,2,6，2,1,56,9};
        
        System.out.println(maxSonArray(arr));
        
    }

    public static int maxSonArray(int [] a){
    
        int max = 0;
        
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i + 1; j < a.length; j++){
                sum += a[j];
                
                if(sum > max){
                    max = sum;
                }
                
            }

        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

运行结果：63

2.找bug

当测试全都是负数的数组时，结果不正确

  public static void main(String[] args) {
        int[] arr = {-8,-2,-6,-2,-1,-24,-9};

        System.out.println(maxSonArray(arr));
    }

    public static int maxSonArray(int [] a){
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i + 1; j < a.length; j++){
                sum += a[j];
                if(sum > max){
                    max = sum;
                }
            }

        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：0

0是我设定的max值，所以此处不能将初始值设定为0.而要设定为范围内最小值，在Java中可以用Integer.MIN_VALUE来表示

3.修正代码

 public static void main(String[] args) {
        int[] arr = {-8,-2,-6,-2,-1,-24,-9};

        System.out.println(maxSonArray(arr));
    }

    public static int maxSonArray(int [] a){
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i + 1; j < a.length; j++){
                sum += a[j];
                if(sum > max){
                    max = sum;
                }
            }

        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出结果：-1

此时代码正确了

四、生成exe文件

这里需要先生成jar文件后通过exe4j软件将jar文件转换成exe文件

但是exe文件打开运行后直接退出了，下一篇文章将会详细描述运行问题及找到的解决方案

五、结语

本文的解法是暴力解法，后续会对其进行优化（使用动态规划来解决），并将针对生成的exe文件没办法成功运行进行解析