我有一个算法问题：
给定一个大小为N的整数数组，找到最大的降幅（不一定连续）：max{array[i]-array[j]}，其中i>j。
简单的解决方案是使用两个循环遍历所有可能的i和j的值，但时间复杂度为O(n*n)。
我认为改进的解决方案是首先映射数组的索引，对数组进行排序，然后遍历数组以找到最大降幅。这个复杂度是O(nlogn)。
是否有一个线性时间复杂度的解决方案？如何实现？
注：我曾经想过一个线性解决方案：创建两个额外的数组，一个记录从开始到结束的给定数组的最大值，另一个记录从结束到开始的最小值。然后，一次遍历两个数组。但是，有人认为这不正确且占用了太多的空间。因此，我想知道更好的解决方案。 - lijuanliu
不使用额外空间的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;
}
您需要追踪两件事情：
您已经看到的最大数字，以及相对于最大数字（即在i元素之前的最大数字减去i元素）所见到的最大降幅。这将在时间上是O(n)，空间上是O(1)。
这个问题恰好是“股票买卖”面试问题，解决方案可以在此处找到：最大单次销售利润
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 ：
1. 然后，max [i]> = arr [j]（因为我们已经通过了它），并且还有
min [i] <= arr [i] - 因此 max [j] - min [j]> = arr [i] - arr [j] ，
算法提供的答案至少与最优解一样好。
2. 另外，由于最大下降是 i，j ，因此不能有任何k＜j
，其中arr [k] ，否则最大下降将是从 arr [k] 到 arr [j] 。
类似地-不能有k> j，使得arr [k] ，出于相同的原因-
因此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 ，v> k，使得max [k] = arr [u]，min [k] = arr [v] ，并且您会得到arr [u] - arr [v]> arr [i] - arr [j] ，这与 i，j 是最大的下降矛盾。
证毕
O(n) 的额外空间。 - amitarr[i]-min >= max_so_far - 如果是，则为新的最大值。很容易看出，它实际上是先前 O(n) 空间版本的 O(1) 空间优化，证明方式非常相似。 - amitpublic static int maxDrop(int[]array){
int maxDrop =0,drop=0,min=array[0];
for(int i=1;i<array.length;i++){
if(array[i]<min){
min=array[i];
}
drop = array[i]-min;
if(drop>maxDrop){
maxDrop=drop;
}
}
System.out.println(maxDrop);
return maxDrop;
}
我只能想到O(nlogn)，但即使复杂度相同，这个方法应该比排序和查找最大降幅更快。
你可以在O(n)的时间内计算相邻数字之间的差异，然后问题就被简化为寻找连续子数组的MAX(sum)，这将是O(nlogn)。