给定未排序的数组,找到A [j] - A [i]的最大值,其中j> i..in O(n)时间

Question

这是一个亚马逊采访问题.我已经使用动态编程在O(n)中解决了这个问题.但我想知道可以有比O(n)更多的优化

例如,假设下面是数组

3 7 1 4 2 4 returns 4

5 4 3 2 1 returns Nothing

4 3 2 2 3 returns 1

这是我编写代码的代码

Answer 1

让我们说你有int A[N].

int res = -1;
int min_value = A[0];
for(int i=1; i<N; i++) {
    // A[i] - A[j] is maximal, when A[j] is minimal value from {A[0], A[1],.., A[i-1]}
    res = max(res, A[i] - min_value);
    min_value = min(min_value, A[i]);
}
return res;

复杂度O(N).

你需要检查N个元素,所以O(N)是你能得到的最好的.

Answer 2

但我想知道可以有更多优化然后O(n)

任何n元素都可以是解决方案的一部分,因此每个元素都需要进行检查.因此,O(n)无法改进.

为了完整起见,这是一个需要O(n)时间并需要O(1)内存的解决方案:

A = [1, 10, 20, -10, 3, 4, 18, 42, 15]

smallest = A[0]
maxdiff = float('-inf')
for x in A[1:]:
  maxdiff = max(maxdiff, x - smallest)
  smallest = min(smallest, x)
print maxdiff