全球网站排名查询网_东莞塘厦招聘网最新招聘_宁波seo网络推广优质团队_爱站网关键词长尾挖掘工具

给定一个非负数组，长度为N.
那么有N-1种方案可以把arr分成两部分。
每一种方案都有 min{左部分累加和, 右部分累加和}
求这么多方案种min{左部分累加和, 右部分累加和}的最大值是多少？

public class Code_BestSplitForAll {public static void main(String[] args) {int N = 20;int max = 30;int testTime = 1000000;System.out.println("测试开始");int c = 0;for (int i = 0; i < testTime; i++) {c++;//System.out.println(i);int len = (int) (Math.random() * N);int[] arr = randomArray(len, max);int ans1 = bestSplit1(arr);int ans2 = bestSplit2(arr);if (ans1 != ans2) {System.out.println(ans1);System.out.println(ans2);System.out.println("Oops!");break;}else{System.out.println("equals");}}System.out.println("测试结束");System.out.println("c="+c);}public static int bestSplit1(int[] arr) {if(null == arr || arr.length == 0){return 0;}int N = arr.length;int ans = 0;for (int i = 0; i < N; i++) {int sumL = 0;for (int j = 0; j <= i; j++) {sumL += arr[j];}int sumR = 0;for (int j = i+1; j < N; j++) {sumR += arr[j];}ans = Math.max(ans, Math.min(sumL,sumR));}return ans;}public static int bestSplit2(int[] arr) {if(null == arr || arr.length == 0){return 0;}int N = arr.length;int ans = 0;int sum = 0;for (int i = 0; i < N; i++) {sum += arr[i];}int sumL = 0;int sumR = 0;for (int i = 0; i < N; i++) {sumL += arr[i];sumR = sum - sumL;ans = Math.max(ans, Math.min(sumL,sumR));}return ans;}public static int[] randomArray(int len, int max) {int[] ans = new int[len];for (int i = 0; i < len; i++) {ans[i] = (int) (Math.random() * max);}return ans;}
}