求整数数组中最大子数组的和(1)

简介: 绝大部分同学都已经做出来了单维数组的 求数组中最大子数组的和, 但是你不妨试一试:把你的程序编译为可执行文件, 然后执行 例如 maxsum.exe 输出就是最大子数组的和, 上面的例子就应该输出 16.

一、前言


活动地址: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;
    }


运行结果:76


7df1215f8ecc42a3a65b563cff9b5bd4.png


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


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;
    }


运行结果:63


1b54099a943148508cde5c54e8e46a3c.png


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;
    }


运行结果:0


c6ac6660c8a64417b11297e4f4b86f1d.png


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


ba6d18979f7c4f20aa4cc88299aba145.png


此时代码正确了


四、生成exe文件


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


c8d20d19a17144e4a5250fa103ed624d.png


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


五、结语


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

相关文章
|
存储 索引
信息学奥赛 如何在整数数组中寻找两数之和等于给定目标值
本文介绍了在整数数组中寻找两个数之和等于给定目标值的问题,提供了两种解法:暴力法和哈希表法。通过比较两种解法的时间复杂度,指出了哈希表法更为高效。
112 0
剑指offer 57. 数组中数值和下标相等的元素
剑指offer 57. 数组中数值和下标相等的元素
98 0
剑指offer 57. 数组中数值和下标相等的元素
|
数据处理
整数数组中最大子数组的和(2)—— 处理二维数组
将二维转化为一维处理,当子矩阵的上下行确定时,把上下行中每一列的数据当作一个单元,确定左右列的过程就是求以列为单元的一维数组的子数组最大和的过程,这种方法大大提高了效率
89 0
整数数组中最大子数组的和(2)—— 处理二维数组
06:整数奇偶排序
06:整数奇偶排序
104 0
|
机器学习/深度学习 存储 算法
【简单算法】1.两数之和,给定整数数组和目标值,找出数组中2数之和等于目标值的元素
【简单算法】1.两数之和,给定整数数组和目标值,找出数组中2数之和等于目标值的元素
【简单算法】1.两数之和,给定整数数组和目标值,找出数组中2数之和等于目标值的元素
|
人工智能
K个逆序对数组
K个逆序对数组
|
测试技术 Python
刷题之给定一个整数数组 nums 和一个目标值 taget,请你在该数组中找出和为目标值的那 两个 整数
今天下午,看了一会github,想刷个题呢,就翻出来了刷点题提高自己的实际中的解决问题的能力,在面试的过程中,我们发现,其实很多时候,面试官 给我们的题,其实也是有一定的随机性的,所以我们要多刷更多的题。去发现问题。
刷题之给定一个整数数组 nums 和一个目标值 taget,请你在该数组中找出和为目标值的那 两个 整数