import java.util.Arrays;

public class Code01_CalcTwoNumDiv {
    public static void main(String[] args) {
        int testTime = 5000; //測試次數(shù)
        int N = 50; //數(shù)組長度
        int range = 1000; //數(shù)據(jù)范圍
        boolean flag = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateArr(N, range);
            int p1 = calcTwoNumDiv(arr);
            int p2 = sortAfter(arr);
            if (p1 != p2) {
                flag = false;
                break;
            }
        }
        System.out.println(flag? "正確" : "錯誤");
    }

    public static int calcTwoNumDiv(int[] array) {
        if (array == null || array.length < 2) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i : array) { //先遍歷一遍數(shù)組，求最大值最小值
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        if (max == min) {
            return 0; //如果最大值和最小值相等，說明這個數(shù)組只有這一個數(shù)據(jù)
        }
        int len = array.length;
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        //遍歷數(shù)據(jù)
        for (int i = 0; i < array.length; i++) {
            int bit = getBit(array[i], len, max, min); //桶的位置
            maxs[bit] = hasNum[bit] ? Math.max(maxs[bit], array[i]) : array[i]; //更新最大值
            mins[bit] = hasNum[bit] ? Math.min(mins[bit], array[i]) : array[i]; //更新最小值
            hasNum[bit] = true; //始終更新為true
        }

        //第一個桶和最后一個桶，肯定是有數(shù)據(jù)的。
        int preMax = maxs[0];
        int res = Integer.MIN_VALUE; //最終的結果
        for (int i = 1; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - preMax);
                preMax = maxs[i]; //更新前一個的最大值
            }
        }
        return res;
    }

    public static int getBit(int num, int len, int max, int min) {
        return ((num - min) * len) / (max - min); //計算num應該存儲在哪個桶
    }

    public static int sortAfter(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }

        Arrays.sort(arr);
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            res = Math.max(res, arr[i] - arr[i - 1]);
        }
        return res;
    }

    public static int[] generateArr(int N , int range) {
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int)(Math.random() * range);
        }
        return arr;
    }
}