最大的leftMax与rightMax之差的绝对值

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

思路一

时间复杂度O(N)，额外空间复杂度O(N)。
从左往右遍历数组，计算left[]表示，以当前位置结尾左边最大值
从右往左遍历数组，计算right[]表示，以当前位置结尾右边最大值
然后遍历这两个数组，求差值绝对值得最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int ans1(int []a){
	int leftNum = Integer.MIN_VALUE;
	int rightNum = Integer.MIN_VALUE;
	int [] left = new int[a.length];
	int [] right = new int[a.length];
	//找左边的最大值
	for(int i = 0; i < a.length; i++){
		if(a[i] > leftNum ){
			left[i] = a[i];
			leftNum = a[i];
		}else{
			left[i] = leftNum;
		}
	}
	//找右边的最大值
	for(int i = a.length-1; i > -1; i--){
		if(a[i] > rightNum){
			rightNum = a[i];
			right[i] = a[i];
		}else{
			right[i] = rightNum;
		}
	}
	//对左右的最大值进行比较
	int maxRes = Integer.MIN_VALUE;
	for(int i=0; i < a.length-2; i++){
		maxRes = Math.max(maxRes, Math.abs(left[i] - right[i+1]));
	}
	return maxRes;
}

思路二

最优解，时间复杂度O(N)，额外空间复杂度O(1)。
找出该数组的最大值，那么其中一组的最大值一定是该值，且另一组最大值应该尽量小，
比如这个最大值是左侧的最大值，那么右侧选右侧的最后一个元素，才能保证差值绝对值最大

代码

1
2
3
4
5
6
7
8
9
10
11
12
public int ans2(int []a){
	//找到数组中的最大值
	int maxNum = Integer.MIN_VALUE;
	for(int i=0; i < a.length; i++){
		if(a[i] > maxNum){
			maxNum = a[i];
		}
	}
	//一个最大值是该数组的最大值，另一个是该组的边界的最小值
	return maxNum - Math.min(a[0], a[a.length - 1]);
}