查找数组连成环形的和最大的连续子数组

思路：

　　把每一种起点情况下的最大子数组之和S求出，存入S[]数组中，最后比较S[]中的最大值（i为数组的长度）存为MaxSum。而此时的起点-finalStart和终点-finalEnd也同样可以在求MaxSum的同时记录下来。

代码如下：

 1 package Test;
 2  
 3 import java.util.Scanner;
 4  
 5  
 6 public class MaxSubArray {
 7     public static void main(String[] args) {
 8         Scanner scan = new Scanner(System.in);
 9          
10          
11
12         System.out.println("输入数组长度");
13         int n = scan.nextInt();
14         int[] a = new int[n];
15          
16         System.out.println("输入数组元素");
17         for(int i = 0;i < n;i++)
18         {
19             a[i] = scan.nextInt();
20         }
21         scan.close();
22     
23         int[] result = maxSub(a,a.length);
24         System.out.println("不连接成环的和最大的连续子数组：");
25         for(int i = result[0];i <= result[1];i++)
26         {
27             System.out.print(a[i] + "	");
28         }
29         System.out.println("和为：" + result[2]);
30      
31      
32          
33          
34        
35       
36         int[] b = new int[2 * n - 1];
37         for(int i = 0;i < n - 1;i++)
38         {
39             b[i] = a[i];
40             b[n + i] = a[i];
41         }
42         b[n - 1] = a[n - 1];
43         int[] result2 = maxSub(b,n);
44         System.out.println("

将数组连成环后的和最大的连续子数组：");
45         for(int i = result2[0];i <= result2[1];i++)
46         {
47             System.out.print(b[i] + "	");
48         }
49         System.out.println("和为：" + result2[2]);
50  
51          
52     }
53      
54      
55      
56      
57   
58     public static int[] maxSub(int[] a,int n)
59     {
60         int an = a.length;
61         int currectSum = a[0];
62         int currectStartIndex = 0;
63         int count = 1;
64         int[] result = new int[3];
65         result[0] = 0;
66         result[1] = 0;
67         result[2] = a[0];
68         for(int i = 1;i < an;i++)
69         {
70             if(currectSum <= 0)
71             {
72                 currectSum = a[i];
73                 currectStartIndex = i;
74                 count = 1;
75             }
76             else
77             {
78                 currectSum += a[i];
79                 count++;
80             }
81             if(currectSum > result[2])
82             {
83                 result[0] = currectStartIndex;
84                 result[1] = i;
85                 result[2] = currectSum;
86             }
87             if(count >= n)
88             {
89                 break;
90             }
91         }
92         return result;
93     }
94      
95      
96      
97 }