算法来查找数组中最大的下拉列表
我有一个算法问题：
给定一个大小为N的数组（假设所有元素都是整数），找到最大的下降（不一定是连续的）：max {array [i] -array [j]}约束：i> j。
简单的解决方案是两个循环并遍历i和j的所有可能值，但时间复杂度为O（n * n）。
我认为改进的解决方案是首先映射数组的索引，对数组进行排序并遍历数组以找到最大的下降。 这个复杂度是O（nlogn）。
有线性时间复杂性的解决方案吗？ 如何？
PS：我曾经想过一个线性的解决方案：创建两个额外的数组，一个是从开始到结束记录给定数组的最大值，另一个是从结尾到开始的最小值。然后，通过两阵一传。 但是，有人认为不正确，占用太大的空间。 所以我想知道更好的解决方案。 - lijuanliu
创建新的2个数组：
max[i] = max { arr[0], arr[1], ..., arr[i] }
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] }
(max is the maximum from first to i, min is the minimum from i to last)
现在，迭代辅助数组并找出最大差异max[i] - min[i]
这需要3次迭代，因此是O(n) 。
正确性证明（指南）：
让最大的下降从指数i到指数j ，其中i<j ：
max[i] >= arr[j] （因为我们已经通过了它），并且min[i] <= arr[i] - 因此max[j] - min[j] >= arr[i] - arr[j] ，并且算法提供的答案至少与最优答案一样好。 i,j ，所以不能有任何k<j使得arr[k] < arr[i] ，因为那么最大的下降将从arr[k]到arr[j] 。 相似 - 由于相同的原因，不能有k>j使得arr[k] < arr[j] - 因此max[j]-min[j] <= arr[i] - arr[j] 从上面我们可以得出结论， max[j]-min[j] = arr[i] - arr[j] 。 所有的都留给一个正式的完整证明是证明，对于每个k你得到max[k]-min[k] <= max[j] - min[j] ，事实确实如此，否则有一些u<k ， v>k使得max[k]=arr[u], min[k]=arr[v] ，并且得到arr[u] - arr[v] > arr[i] - arr[j] ，这与i,j是最大下降的事实相矛盾。
QED
你需要跟踪两件事情：
你所拥有的最大数量似乎达到了元素i，并且相对于最大数量（即i之前的最大数量减去元素i）而言，最大的下降似乎是最大的。 这将是O（n）在时间和O（1）在空间。
这个问题恰恰是“股票买/卖”面试问题，解决方案可以在这里找到：最大单一销售利润
O（n）解决方案无额外空间：
public int maxDrop(int[] a) {
int max = a[0];
int maxDrop = -1;
for (int i = 0; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
}
else {
int drop = max - a[i];
maxDrop = Math.max(maxDrop, drop);
}
}
return maxDrop;
}