你的位置:首页 > Java教程

[Java教程]返回一个整数数组中最大子数组的和(有环)


1.设计思想  

  (1)首先创建一个一维数组a[],根据用户输入的数组长度及数组内容进行存储数据。

  (2)再定义几个变量,sum用于求和,max为和最大值,num为数组长度。

  (3)开始for循环,sum初始化为0,max初始化为a[0]。循环内容为sum+=a[i];如果sum比max大则将sum值赋给max,如果sum小于0,则定义sum=0。直至循环结束,得到最大子数组的和。

  (4)寻找a数组最小值,得到其下标j,将j值赋给t。创建数组b,进行两次循环,第一次循环i=0,每循环一次j值就增加1,b[i]=a[j],当j>=num时,第一次循环结束。进行第二次循环,令sum=0,j=0。每循环一次j值就增加1,b[i]=a[j],当j>=t时,循环结束,便成环。

  (5)开始for循环,sum初始化为0,max为未成环之前得到的最大值。循环内容为sum+=b[i];如果sum比max大则将sum值赋给max,如果sum小于0,则定义sum=0。直至循环结束,得到最大子数组的和。

2。源程序代码

 1 //返回一个一维整数数组最大子数组和最大值(有环) 2 package ketang; 3 import java.util.*; 4 public class SumArray { 5   public static void main(String[] args) { 6     Scanner sca=new Scanner(System.in); 7     System.out.println("输入整数数组数的个数"); 8     int num=sca.nextInt(); 9     int a[],b[];10     a=new int[num];11     b=new int[num];12     System.out.println("输入数组的数");13     int i;14     for(i=0;i<num;i++)15     {16       a[i]=sca.nextInt();17     }18     int t,j=0,sum=0,max=a[0];19     for(i=0;i<num;i++) //未成环之前找最大值20     {21       sum+=a[i];22       if(max<sum)23       {24         max=sum;25       }26       if(sum<0)27       {28         sum=0;29       }30     }31     /* 实现首尾相接 */32     int min=a[0];33     for(i=0;i<num;i++) //找到最小值34     {35       if(min>a[i])36       {37         min=a[i];38         j=i;39       }40     }41     t=j;  //将最小值下标j值赋给t42     i=0;43     while(j<num)44     {45       b[i]=a[j];46       i++;47       j++;48     }49     j=0;50     while(j<t)51     {52       b[i]=a[j];53       i++;54       j++;55     }56     sum=0; //接着初始化sum为057     for(i=0;i<num;i++) //连成环之后找最大值58     {59       sum+=b[i];60       if(max<sum)61       {62         max=sum;63       }64       if(sum<0)65       {66         sum=0;67       }68     }69     System.out.println("最大子数组和为 "+max);70   }71 }

The Main Code

3.结果截图

4.编程总结

  此次编程只需在原来程序基础上进行改进即可,难点在于如何找到连成环的关键位置,关键位置找到后形成一个新数组,再利用上次的思想进行寻找最大值即可。

5.psp