求解数组环中最大子数组和的问题(java)

//石家庄铁道大学    信1405-1 班   唐炳辉

在上一次作业中，对于普通数组的最大子数组的求解问题的基础上，将普通的数组变成一个首尾相接的环，求这个环的最大子数组。类似的，只要改变普通数组的数组位置，在依次进行求解就行了。。。例如

　　　　　　　　给定你一个数组 -1 2 -5 6 7 让你求这个环的最大子数组，，可以用下边这个函数来实现转化，，具体转化完，就生成五个新的数组，分别问

　　　　　　　　　　　　　　　　-1 2 -5 6 7
　　　　　　　　　　　　　　　　2 -5 6 7 -1
　　　　　　　　　　　　　　　　-5 6 7 -1 2
　　　　　　　　　　　　　　　　6 7 -1 2 -5
　　　　　　　　　　　　　　　　7 -1 2 -5 6 　　

这样对这几个数组分别求出他们中的最大子数组，再找出所有中的最大子数组即可

　　　核心函数

 int Arr1[]=new int [flase0g];
        for(int i =0;i<flase0g;i++)
        {
            for(int y=0;y<flase0g;y++)
            {
                Arr1[y]=Arr[(y+i)%(flase0g)];
            }
        
             MAX=f.findMaxArr(Arr1);
             
            if(MAX>MAX1)
            {
                MAX1=MAX;
            }
        }

　　　　　　　　　下边是具体的实现代码　　　　

  1 //石家庄铁道大学    信1405-1 班   唐炳辉　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　：三藏
  2 /**给定一个数组，将这个数组首位相连，构成一个环，求出这个数组环中子数组的最大值，**/
  3  package ZiShuZu;
  4 import java.util.Scanner;
  5 
  6 
  7  
  8 public class HuanShuzu {
  9 
 10 
 11 
 12 public static void main(String[] args) {
 13     HuanShuzu f = new HuanShuzu();
 14         
 15     //用户自己定义数组的长度并 自行输入一串数组
 16         int MAX = 0;
 17         int MAX1=0;
 18         Scanner in=new Scanner(System.in);
 19         System.out.print("请输入数组长度：");
 20         int flase0g=in.nextInt();
 21         //输入数组中的各个数值
 22         System.out.print("请依次输入整数：");
 23         int Arr[]=new int[flase0g];
 24         for(int i=0;i<flase0g;i++)
 25         {
 26             Arr[i]=in.nextInt();
 27         } 
 28         //输出用户输入的数组  
 29         System.out.print("您输入的数组环为 ");
 30         for(int i=0;i<flase0g;i++)
 31         {
 32             System.out.print(Arr[i]+"  ")  ;
 33         }  
 34         System.out.println(" ")  ;
 35         int Arr1[]=new int [flase0g];
 36         for(int i =0;i<flase0g;i++)
 37         {
 38             for(int y=0;y<flase0g;y++)
 39             {
 40                 Arr1[y]=Arr[(y+i)%(flase0g)];
 41             }
 42         
 43              MAX=f.findMaxArr(Arr1);
 44              
 45             if(MAX>MAX1)
 46             {
 47                 MAX1=MAX;
 48             }
 49         }
 50         
 51         
 52         //双重数组
 53         System.out.print("最大的数组为"+MAX1);
 54         
 55         //输出最后的结;
 56     
 57     }
 58 
 59     public int findMaxArr(int[] arr) {
 60         int Arr = 0;//用来记录当前并入的数组的和
 61         int MaxArr = 0;//用来记录之前的最大的数组和
 62         int A = arr.length;
 63         int Location1=0;
 64         int Location2=0;//用来记录子数组的最后一个位置
 65         
 66         int i;
 67         
 68 
 69     /**核心算法，两个变量 ，一个记录当前并入的数组的值，另外一个记录所算过得最大的数组的值
 70         当并入的值为小于零的时候，就没必要进行继续的相加了，因为再加也不可能比后边单独
 71         的数字大，所以，为负数就重新刷新位置，重置子数组的长度重新去找一个新的子数组**/
 72         for ( i = 0; i < A; i++) {
 73             Arr += arr[i];
 74             if (Arr < 0) {
 75                 Arr = 0;
 76                 
 77                 
 78                 }
 79             if (Arr > MaxArr) {
 80                 MaxArr = Arr;
 81                 Location2=i;
 82                 ;
 83                 }
 84         }
 85         
 86         //用这个算法，通过最后的位置，和最大值来求出起始位置
 87         for(i=Location2;i>=0;i--)
 88         {
 89             if(MaxArr-arr[i]==0)
 90             {    
 91                 Location1=i;//通过求出来的最大值和最后的那个位置，往前推移，找出起始位置
 92                 break;//跳出循环
 93             }
 94             
 95         }
 96         /**这种情况的出现当且仅当全部的数字都为负数的时候，
 97          对所有的数字求一个最大值就是最大子数组**/
 98         if (MaxArr == 0) {
 99             for ( i = 0; i < A; i++) {
100                 
101                 if (i == 0) {
102                     MaxArr = arr[i];
103                 }
104                 if (arr[i] > MaxArr) {
105                     MaxArr = arr[i];
106                 }
107             }
108         }
109         //***************
110 
111         return MaxArr;
112         
113     }
114 }

实验截图