方法设计-循环数组求最大子数组

 1 package Demo;
 2 //2017.3.31
 3 //实验目的：实现的是一个循环数组，求他们的连续的最大子数组的和的最大值，数组中可以包含负数
 4 //实验思路：这个可以先想一想如果不是循环数组的话，一个普通的数组，求他们的连续的最大子数组的和的最大值，应该怎么实现，
 5 //循环数组跟普通数组不一样的地方在于数组的后面的元素，能和他之前的数相联系，例如：1,2,3,4,5 如果是一个循环数组，
 6 //那么其中的3，可以组成的数组最大就不是3,4,5，而是3,4,5,1,2 总而言之，就是循环数组想从那个数开始，那么相当于
 7 //在这个数的位置切开，他的最大子数组，就是和他相邻的但是断开后不相邻的那个位置，例如从4开始，和4相邻的是3和5，当截断后
 8 //可以看成是一个普通数组4,5,1,2,3，其中的3就是和他相邻但是截断后不相邻的数，
 9 //如果想求这个数组，我们可以把这个数组扩展一下，如1,2，3,4,5我们可以扩展成1，2,3,4,5,1,2，3,4 ，也就是在最后一个数
10 //的后面再加上他前面的数，然后我们在取最长的子数组的时候，可以按照第二个新构建的数组，从其中取连续的五个，这个是满足要求的数组
11 
12 public class shuzu2 {
13     public static void main(String[]args)
14     {
15         int a[]={1,2,3,4,5};//任意定义的一个数组
16         int b1[] = new int[2*a.length-1];
17         for(int i=0;i<a.length;i++)
18         {
19             b1[i]=a[i];
20         }
21         for(int i=a.length;i<2*a.length-1;i++)
22         {
23             b1[i] = a[i-a.length];
24         }
25         int b[]=panduan(a);
26         System.out.println("最大子数组是");
27         for(int i=b[1];i<=b[2];i++)
28         {
29             System.out.print(b1[i]+"	");
30         }
31         System.out.println("
最大值是："+b[0]);
32     } 
33     static int[] panduan(int[] a)
34     {
35         int b[] = new int[2*a.length-1];
36         for(int i=0;i<a.length;i++)
37         {
38             b[i]=a[i];
39         }
40         for(int i=a.length;i<2*a.length-1;i++)//产生一个数组，让其长度是a数组长度的2倍-1，里面存的数据是a和a的长度减去最后一个
41         {
42             b[i] = a[i-a.length];
43         }
44         int [][]a1= new int[b.length][b.length];//用这个二维数组记录开始和结束的位置，以便于最后统计子数组的数据
45         for(int i=0;i<a.length;i++)
46         {
47             for(int j=i;j<b.length&j-i<a.length;j++)//对二维数组进行初始化
48             {
49                 a1[i][j]=0;
50             }
51         }
52         for(int i=0;i<a.length;i++)
53         {
54             for(int j=i;j<b.length&j-i<a.length;j++)
55             {
56                 if(j==i)
57                 {
58                     a1[i][j]=b[j];//如果i等于j说明这个子数组长度为1
59                 }
60                 else
61                 {
62                     
63                     a1[i][j]+=b[j]+a1[i][j-1];//让这个数组从开始位置加到结束的位置，实现方式是让他加上他前一个数再加上循环到这个位置的数
64                 }
65             }
66         }
67         //将所有子数组的值的和存好以后，开始判断这些子数组那一个最大
68         int max=a1[0][0];
69         int i1=0;
70         int j1=0;
71         for(int i=0;i<a.length;i++)
72         {
73             for(int j=i;j<b.length&j-i<a.length;j++)
74             {
75                 if(max<a1[i][j])
76                 {
77                     max=a1[i][j];
78                     i1=i;
79                     j1=j;
80                 }
81             }
82         }
83         int a2[]=new int[3];//定义三个长度，分别用来存去最大子数组的和的值，子数组的开始位置和结束位置
84         a2[0]=max;
85         a2[1]=i1;
86         a2[2]=j1;
87         return a2;
88     }
89 }