前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个长度为n的数组，其中将数组能够分割成两个不同的子数组，假设左边arr[0…k]，最大值为leftMax,右边arr[k…n-1]最大值为rightMax，求所有的分割方案中，rightmax-leftmax绝对值的最大值是多少？
如：arr = {2,7,3,1,1}
结果为：6

解决方案

原问题：
解法一：
穷举法：略
解法二：常规预处理解法，必须要会
1、申请两个数组，left和right数组，left[i]表示[0…i]中的最大值，right[i]表示[i…arr.len-1]的最大值，填充数组只需要遍历一次即可
2、再次遍历数组即可获取到结果时间可缩减到O(n)，空间O（n）
最优解：
1、获取到arr中的最大值max
2、直接返回max - Math.min(arr[0], arr[arr.len-1])

代码编写

java语言版本

原问题：
方法二:

    /**
     * 二轮测试：
     * 方法二：常规优化，预处理数组
     * @param arr
     */
    public static int getMaxSubCp2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // left[i]表示左边[0...i]最大值
        int[] left = new int[arr.length];
        // right[i]表示右边[i...arr.lenght-1]的最小值
        int[] right = new int[arr.length];
        fillLeftAndRight(left, right, arr);
        // 获取最值
        int res = 0;
        for (int i = 0; i < arr.length-1; i++) {
            int leftMax = left[i];
            int rightMin = right[i+1];
            res = Math.max(res, Math.abs(leftMax - rightMin));
        }
        return res;
    }

    /**
     * 填充left和right
     * @param left
     * @param right
     * @param arr
     */
    private static void fillLeftAndRight(int[] left, int[] right, int[] arr) {
        int maxL = Integer.MIN_VALUE;
        int maxR = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            // 更新最值
            maxL = Math.max(maxL, arr[i]);
            maxR = Math.max(maxR, arr[arr.length - 1 - i]);
            left[i] = maxL;
            right[arr.length-1-i] = maxR;
        }
    }

最优解：

    /**
     * 二轮测试：
     * 方法三：最优解
     * @param arr
     */
    public static int getMaxSubCp3(int[] arr) {
        int max = getMaxOrMin(arr, 0, arr.length, "max");
        return max - Math.min(arr[0], arr[arr.length-1]);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、首先说一下这道题的方法二解法，其实每道题基本都能暴力解法求一下，当我们发现在暴力解法的情况下存在多余的循环，比如这道题中存在每一种情况都需要重新循环，那么我们是否就可以想一下是否能够预处理一下数组，能够将每一种情况下不用重新循环就能获取到最值，也就是空间换时间的方式。
2、其次就是我们的最优解法，首先为什么是最大值减去两边的最小值呢？从问题出发我们求的是两边最大值之间的绝对值的最大值，那么相减的时候一定有一边是存在全局最大值的！比如例题中，7一定存在于左边或者右边的数组中，被减数一定是最大值7，那么现在看减数是谁，首先减数是另一边的最大值，假设另一边为右边，那么如果右边子数组的最大值大于arr[arr.len-1],那么 7-max的结果一定是小于7-arr[arr.len-1]的，其次如果右边子数组最大值小于arr[arr.len-1]显然是不可能存在这种数的，因为最大值小于arr[arr.len-1]的话，arr[arr.len-1]就是最大值了。。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！