找到随机数组的最大增量

Question

假设我有一个随机实数的数组,我如何将指数配对(i, j)在哪里j<i和

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

没有提示递归.所以我想在n nn n sort中排序数组.但是,排序数组的min和mix可能不满足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]);
}