软件工程结对开发——一维最大子数组求和溢出问题
一、题目要求
题目:返回一个整数数组中最大子数组的和。
要求：
要求程序必须能处理1000 个元素；
每个元素是int32 类型的；
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
二、设计思路
将数组第一个和第二个数置为2的63次方，观察结果是否溢出。
三、源代码
1 package com.java.lianxi; 2 3 import java.util.Scanner; 4 5 public class lianxi4 { 6 public static void main(String[] args) 7 { 8 int num,i; 9 long sum=0; 10 long max; 11 Scanner cin=new Scanner(System.in); 12 System.out.print("请输入数组的长度："); 13 num=cin.nextInt(); 14 long array[]=new long[num]; 15 array[0]=(long)Math.pow(2,63); 16 array[1]=(long)Math.pow(2,63); 17 max=array[0]; 18 for(i=2;i<num;i++) 19 { 20 if((int)(Math.random()*2)==0) 21 { 22 array[i]=(long)(Math.random()*100000000); 23 } 24 else 25 { 26 array[i]=-(long)(Math.random()*100000000); 27 } 28 } 29 for(i=0;i<num;i++) 30 { 31 if(sum<=0) 32 { 33 sum=array[i]; 34 } 35 else 36 { 37 sum=sum+array[i]; 38 } 39 if(sum>max) 40 { 41 max=sum; 42 } 43 } 44 if(max==(long)Math.pow(2,63)) 45 { 46 System.out.println("大数溢出"); 47 System.out.print("子数组和的最大值为："+max); 48 } 49 else 50 { 51 System.out.print("子数组和的最大值为："+max); 52 } 53 } 54 55 }
四、运行结果截图
五、心得体会
通过测试，发现当溢出时，最大子数组的和恒为2的63次，也就是long型所能表示的最大整数，出现大数溢出，所得的不是我们想要的结果。
我们想了很久也没有想出来有什么解决办法，因为数据类型所能表示的数就那么大，但是如果想得到正确的结果，我们可以不输出一个最终结果，可以输出几个数相加，
但是考虑到相加的几个数都要控制在2的63次方之内。
还想了一个就是可以把最后结果当成两个变量来显示，高位放在其中一个变量，低位放在另一个变量，但是我们都没有实现。