一、前言
活动地址: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
接着我测试了一个有正有负的数组,结果也正确
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
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
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
此时代码正确了
四、生成exe文件
这里需要先生成jar文件后通过exe4j软件将jar文件转换成exe文件
但是exe文件打开运行后直接退出了,下一篇文章将会详细描述运行问题及找到的解决方案
五、结语
本文的解法是暴力解法,后续会对其进行优化(使用动态规划来解决),并将针对生成的exe文件没办法成功运行进行解析