算法-面试题系列 - 求数组左部分最大值减去右部分最大值的绝对值

给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。

但是每种划分下都有左部分的最大值和右部分的最大值

请返回最大的，左部分最大值减去右部分最大值的绝对值。

算法流程

1. 第一步：找到数组arr中的最大的数字Max。
2. 第二步：比较arr[0],arr[N-1]的大小
3. 第三步： max - Math.min(arr[0], arr[arr.length - 1])

我们要求左边最大减去右边最大，max肯定是在左边数组和右边数组中的最后参与决策的最大数。

image-20210522185617736

假设12在左边数组中，右边数组剩下[5,6,7]

image-20210522190107938

因为把max放入了左边的数组，所以，我们需要右边数组的最大值尽可能的小，数组个数越少，他的最大值就是尽可能的小，比如剩下[5,6,7]的情况，我们可以看到我们区arr[N-1]这个数作为右侧数组，是最满足 左部分最大值减去右部分最大值的绝对值条件的。

同理 把max划分到右侧数组，左侧数组a[0]划分是最符合条件的。

ublic class MaxABSBetweenLeftAndRight {

    public static int maxABS1(int[] arr) {//暴力方法，每个分割点求最大值
        int res = Integer.MIN_VALUE;
        int maxLeft = 0;
        int maxRight = 0;
        for (int i = 0; i != arr.length - 1; i++) {
            maxLeft = Integer.MIN_VALUE;
            for (int j = 0; j != i + 1; j++) {
                maxLeft = Math.max(arr[j], maxLeft);
            }
            maxRight = Integer.MIN_VALUE;
            for (int j = i + 1; j != arr.length; j++) {
                maxRight = Math.max(arr[j], maxRight);
            }
            res = Math.max(Math.abs(maxLeft - maxRight), res);
        }
        return res;
    }

    public static int maxABS2(int[] arr) {//预处理数组，单调窗口加速
        int[] lArr = new int[arr.length];
        int[] rArr = new int[arr.length];
        lArr[0] = arr[0];
        rArr[arr.length - 1] = arr[arr.length - 1];
        for (int i = 1; i < arr.length; i++) {//预处理数组，从左到右 i点的左侧最大值
            lArr[i] = Math.max(lArr[i - 1], arr[i]);
        }
        for (int i = arr.length - 2; i > -1; i--) {//预处理数组，从右到左，i右侧的最大值
            rArr[i] = Math.max(rArr[i + 1], arr[i]);
        }
        int max = 0;
        for (int i = 0; i < arr.length - 1; i++) {//每个分割点求最大值
            max = Math.max(max, Math.abs(lArr[i] - rArr[i + 1]));
        }
        return max;
    }

    public static int maxABS3(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        return max - Math.min(arr[0], arr[arr.length - 1]);//数组最大值 -min(arr[0],arr[N-1])
    }

    public static int[] generateRandomArray(int length) {
        int[] arr = new int[length];
        for (int i = 0; i != arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000) - 499;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray(200);
        System.out.println(maxABS1(arr));
        System.out.println(maxABS2(arr));
        System.out.println(maxABS3(arr));
    }
}