algorithm - 找到随机数组中的最大增量

Question

假设我有一个随机实数数组，我如何得到索引对 (i, j)其中 j<i和

maximise (a[j] - a[i])在 O(n ln(n))时间

n ln n 建议递归。所以我在考虑对数组进行 n ln n 排序。但是排序数组的最小值和混合可能不满足 j<i

区别a[j]-a[i]取决于所有 i ， j 所以扫描所有可能的排列是 O(n^2) .有人对我如何划分问题空间有什么建议吗？

Answer 1

如果我没理解错的话，你想找max(a[j] - a[i])在所有对中(i, j)其中 j < i .

你可以在 O(n) 内完成，没有太大问题。

对于每个索引 i , 最大化 a[j] - a[i]我们需要找到 max(a[j]) 的表达式间隔 [0 .. i - 1] .因此，让我们从左向右移动(增加 i )并保持当前最大值 a[j] .

int maxa = a[0];
for (int i = 1; i < n; ++i) {
    int current = maxa - a[i];
    if (current > best) {
        best = current;
    }
    maxa = max(maxa, a[i]);
}