左右差值绝对值最大

发表于 | 分类于 ，

题目

给定一个长度为N(N>1)的整型数组arr，可以划分成左右两个部分，
左部分arr[0..K]，右部分arr[K+1..N-1]，K可以取值的范围是[0,N-2]。
求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，
最大是多少？例如[2,7,3,1,1]，当左部分为[2,7]，右部分为[3,1,1]时，
左部分中的最大值减去右部分最大值的绝对值为4。当左部分为[2,7,3]，
右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为6。
还有很多划分方案，但最终返回6。

1
2
3
4
5
6
7
8
public static int maxABS(int[] arr){
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
    }
    return max - Math.min(arr[0], arr[arr.length - 1]);

}

最优解，时间复杂度O(N)，额外空间复杂度O(1)。先求整个arr的最大值max，
因为max是全局最大值，所以不管怎么划分，max要么会成为左部分的最大值，
要么会成为右部分的最大值。如果max作为左部分的最大值，
接下来我们只要让右部分的最大值尽量小就可以了。
右部分的最大值怎么尽量小呢？
右部分只含有arr[N-1]的时候就是尽量小的时候。同理，
如果max作为右部分的最大值，只要让左部分的最大值尽量小就可以了，
左部分只含有arr[0]的时候就是尽量小的时候。
所以整个求解过程会变得异常简单