一道算法题: 求一个数组中最大的 abs(max(left) - max(right))

[eyp82]

前几天碰到一道算法题, 由于限定时间感觉没有做好: 一个长度为 N 的数组 Arr, 可以按照其中的某个元素 K 做为分界点 0<=K<N, 得到其左边部分所有元素最大值(包括 K) 减去 右边部分最大值(不包括 K)的绝对值 ABS. 需要写一个函数求助该数组中这个绝对值 ABS 最大是多少. 公式如下: max(abs(max{Arr_0, ... Arr_K} - max{Arr_K+1, ...Arr_N-1})) for K in (0...N-1)

要求写出时间 /空间复杂度均为 O(N)的算法, 但是我想了半天, 每次往右移动 K 取值的时候, 都要重新对右边的元素进行排序啊, 不知道怎么才能 O(N).

请教各位大神.

[dikcen]

这个，不等于 max(Arr)-min(Arr)吗？

[dikcen]

错了，请无视

[casparchen]

就是 O （ n ）啊，先找到波峰，然后往后找波谷。

[Dwayne]

扫一次求最大值 再扫一次求解也是 O(n) 吧

[jky]

顺序遍历计算并保留每个元素左边的最大值，然后逆序遍历计算最大值减去对应左边的最大值。

[jonah]

找到最大值，然后分别比较跟头尾之差哪个大，粗略想了一下。等下再细想

[neosfung]

建一个长度为 N 的数组 t_arr 。
第一轮是正向遍历， t_arr[i]表示的是，在 arr[0~i+1]中的最大值
第二轮是反向遍历，求 max(abs(max(arr[i+1 ~ N-1])), t_arr[i])

[veryflying]

假设原数组 arr,设两个辅助数组 a ， b ， a[i]表示 max(arr[0...i])， b[i]表示 max(arr[i...arr.length])，然后扫描一遍 a 和 b 就可以了，时间空间都是 O(n)。

[xyzw]

答案是 abs(max(arr) - min(arr[0], arr[N-1]))嗎？

[neosfung]

#7 下标标错了，不知道怎么改，希望楼主能理解

[casparchen]

@xyzw 不是。
首先，左边的最大数一定是数列中某一个波峰，但是不一定是最大的那个。所以记录当前最大波峰，然后动态更新最大差值就好。

[veryflying]

@veryflying 后来想一下，一个数组也可以。。

[uoryon]

@veryflying 嗯。确实。

[ryd994]

@jonah +1 每错就是这样
因为不论分界线是哪个：
1.如果全局 max 在分界线左，则右 max 大于左 max ，则左右 max 差取决于左 max 最小，反之同理
2. 从左向右移动分界线，左 max 单调递增，右 max 单调递减。反方向同理。
3. 因此分界线必定在两端之一，比较一下两端哪个小，和全局最大相减即可

[ryd994]

@casparchen 不对，最大数一定是全局最大，只不过最大 max 差可能是左减右或是右减左

[eyp82]

@casparchen 谢谢, 你的思路很好, 但感觉有个问题, 因为最后要求绝对值, 所以未必波峰-波谷就最大吧, 有可能左边比右边小, 得到一个很大的负数, 反而比波峰-波谷要大.

[hd7771]

从左往右扫，
这个时候分别维护一个最大值和一个最小值，
用当前的数与最大值和最小值差求 abs ，
更新答案，
更新最大值和最小值。

[xyzw]

@casparchen 假設最大數在分段 K 的左邊，結果是 max(arr) - max(arr[K..N-1])，小於等於 K=N-1 時的 max(arr) - arr[N-1]
假設最大數在分段時的右邊，結果是 abs(max(arr[0..K-1]) - max(arr))=max(arr) - max(arr[0..K-1])，小於等於 K=0 時的 max(arr) - arr[0]
要不 K=0 ，要不 K=N-1

[hd7771]

至于为什么维护最大值和最小值，你用贪心去反证。
如果我这个解最优那么比他小或者比他大是不是更好呢？没错就是更好。

[eyp82]

@jky
@neosfung

我想了一下你们的思路, 感觉你们是对的, 我当时没想到可以逆序遍历, 非常感谢.