一道算法题: 求一个数组中最大的 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).

请教各位大神.

[ryd994]

md 我大概今天脑子冻傻了
slice 右边开区间
max( [abs(max(a[:K+1])-max(a[K+1:])) for K in range(n-1)] )

[juxingzhutou]

1. 先正向遍历一遍 Arr ，求出一个长度为 N 的数组 asc ， asc = {n | n = max{Arr[0..k]}, k∈[0..N-1), k∈N(自然数)}， asx[i]就等于 Arr[0..i]中的最大值
2. 再反向遍历一遍 Arr ，求出一个长度为 N 的数组 desc ， desc = {n | n = max{Arr[k..N-1]}, k∈(0..N], k∈N(自然数)}， desc[i]就等于 Arr[i+1..N-1]中的最大值
3. 遍历 i in range(0..N-2)，找出 abs(asc[i] - desc[i])的最大值

算法复杂度 3n ，符合你 O(n)的要求。

优化：步骤 2 和步骤 3 可以合并在一起，不用单独创建一个数组 desc

[bidongliang]

这个值在交易中叫最大回撤， O(n)算法，从后向前扫描，维护当前看到的最小值和扫描位置元素与当前最小值的差，结果就是所求。

[random123]

@jonah
@jky
@neosfung
@veryflying
@xyzw
@ryd994

如果没猜错的话, 楼主名字的简写是 ZX, 我是原来安排的面试官之一. 我们很喜欢好学的人, 如果是你的话, 我会和别的 team 再讨论一下你的简历.

另外这道题我自己当时做也是#7 的解法, 但其实觉得逆序遍历才更符合计算机的思维, 更普适. 我回复的这几位如果想去外资 IT 工作的话可以留下邮箱地址, 我来安排面试, 我们提供一流的薪水, 期权和办公环境, 顶配 rMBP, Apple 外接显示器, 不加班. 尤其欢迎有数据库核心开发经验和喜欢敏捷开发的朋友. 工作地点在北京中关村.

[AlisaDestiny]

你求最大值不一定要排序吧。用变量记录一下就好。移动 K 的时候比较下记录与新值的大小。

[liprais]

这是 pivotal 的面试题吧

[LukeEuler]

@ryd994 正解。而且空间复杂度是 O(1)

[hanzichi]

遍历的时候，可以得到前 n 个的最值，那么，反向遍历的时候，同样可以得到后 n 个的最值。。

其实再不济， ST 预处理下， O （ nlogn ）也能解。。 https://github.com/hanzichi/algorithm-js/blob/master/RMQ-ST.js

[hst001]

@casparchen 不一定是波峰

[ryd994]

@random123 一脸懵哔，我只是个还没毕业应届而已啊

[ryd994]

@juxingzhutou
@hanzichi
想到这里很不错，但是再往前一步
请看我 28 楼
最小 max 一定在两端
其他地方可能存在相等，不可能更优

[hanzichi]

@ryd994 #51 666 这波可以

[jky]

@random123 谢谢，不过目前没有换工作的计划:P 。

[juxingzhutou]

@ryd994 恩，你这个解法确实更好，可以优化常系数。

[juxingzhutou]

@bidongliang 最大回撤不是这个意思，最大回撤是选的最大跌幅区间，是(最大值 - 最小值)最大的区间。

[uucloud]

确实。。第一反应是#5 楼的解法扫两遍，不过#14 的解法更巧妙，只扫一遍就好。

[popbones]

不知道我是否理解了题目。

是要求所有可能的分割中最大的子串最大值的绝对差吗？

因为分两段，其中一段的最大值肯定是全局最大值，另一段的最大值一定大于等于这一段的两个端点值中的最小值

为了让第二段最小，则设第二段的大小为 1 ，所以第二段要么是数组的第一个值，要么是数组的最后一个值，因为包含更多的值只会增大这一段的最大值或对这一段的最大值没有影响。

这样的话就扫一遍得出全局最大，跟两个断电比一下，然后几个 if-elas 就好了 https://play.golang.org/p/1IpfFujqfh

[justyy]

这 C++题解在这里: https://helloacm.com/an-interview-question-on-algorithm-to-find-absmax-left-max-right/