【算法证明含证明过程】数组左部分中的最大值减去右部分最大值的绝对值,最大是多少?

时间:2021-02-02 15:10:44
题目描述:给定一个长度为N的整型数组arr,可以划分成左右两个部分: 左部分arr[0..K],右部分arr[K+1..arr.length-1],K可以取值的范围是[0,arr.length-2] 求这么多划分方案中,左部分中的最大值减去右部分最大值的绝对值,最大是多少? 例如: [2,7,3,1,1] 当左部分为[2,7],右部分为[3,1,1]时,左部分中的最大值减去右部分最大值的绝对值为4; 当左部分为[2,7,3],右部分为[1,1]时,左部分中的最大值减去右部分最大值的绝对值为6; 最后返回的结果为6。 注意:如果数组的长度为N,请尽量做到时间复杂度O(N),额外空间复杂度O(1)。证明如下算法的正确性:

算法步骤:1. 求出数组中最大的元素,记为MAX;2. 记MIN = min(arr[0],arr[arr.length-1]);3. MAX - MIN即为所求。

证明如下:记左部分最大值和右部分最大值中较大的一个为bigMax,较小的一个为smallMax。由题即求bigMax-smallMax的最大值。由式bigMax-smallMax可知,bigMax越大,smallMax越小则bigMax-smallMax值越大。故bigMax必为数组中的最大值,记为MAX。假设现在以MAX作为划分点,并假设MAX左右均有元素存在(若MAX为arr[0]或arr[arr.length-1]同理)。现在考虑以MAX为划分时,左部分的情况:将左部分分为arr[0]和从arr[0]到MAX的两部分,若arr[0]是左部分的最大值,则smallMAX就选arr[0](在这种情况下,假设不以MAX为划分,而以MAX左边的某一个元素划分,由于必有smallMAX<MAX,smallMAX仍要选arr[0])。否则若arr[0]不是左部分的最大值,由于要使得smallMAX越小越好而此时左部分的最大值必然是存在于arr[1]到MAX之间的某个值,只有选arr[0]为smallMAX并以arr[1]为划分才能使得bigMax-smallMax值越大(可以证明,除此之外的划分无论如何仍然要选arr[0]为smallMAX)。综上,左部分的最大值无论如何都是选arr[0]。另外,若要使得某一部分的值既是这一部分的最大值,又是这一部分的最小值。那么只有当这一部分只含有一个元素时,这个元素同时满足这两个条件。同理可证明右部分最大值无论如何都是选arr[arr.length-1]。综合考虑smallMax= min(arr[0],arr[arr.length-1])。由此得证。


 public int getMaxABSLeftAndRight(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]);

}