数据结构与算法--这么多方案中min左部分累加和右部分累加和的最大值是多少

给定一个非负数组，长度为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;
    }
}

原文地址：https://blog.csdn.net/m0_37564426/article/details/143698416

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！