java - 给定一个未排序的数组，在 O(n) 时间内找到 A[j] - A[i] 的最大值，其中 j>i..

Question

这是一个 Amazon 面试问题。我已经使用动态在 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

这是我写的代码Code

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) 是您能得到的最好结果。