设计思路:依次将最后一个元素调到第一位,将各元素向后移,之后循环,形成数组长度个新的一维数组,并对每个数组求最大子数组的和,之后把每个一维数组的最大子数组的和存到一个数组A里面,对A求最大值,即为此循环数组的最大子数组;
代码:
package sum4; import java.util.Scanner; public class sum { static int GetMaxAddOfArray(int arr[], int sz) { if (arr ==null || sz <= 1) return 0; int b[]=new int[arr.length]; int c[]=new int[arr.length]; int max=c[0]; for(int a=arr.length-1;a>0;a--) { for(int j=0;j<arr.length;j++) { b[j]=arr[a]; a=(a+1)%arr.length; } int MAX = b[0]; int sum = b[0]; for (int i = 1; i < sz; i++) { if (sum < 0) sum = b[i]; else { sum += b[i]; } if (sum > MAX) MAX = sum; } c[a]=MAX; } for(int m=1;m<arr.length;m++) { if(c[m]>max) max=c[m]; } return max; } public static void main(String[] args) { Scanner input=new Scanner(System.in); int n; System.out.println("输入数组个数:"); n=input.nextInt(); int i; int arr[]=new int[n]; for(i=0;i<n;i++) { arr[i]=input.nextInt(); } input.close(); System.out.println(GetMaxAddOfArray(arr,n)); } }
实验截图: