найти максимальное увеличение случайного массива

Question

Предположим, у меня есть массив случайных вещественных чисел, как мне пара индексов (i, j), где j<i и

maximise (a[j] - a[i]) в O(n ln(n)) время

n ln nРекомендованные рекурсии.Так что я думал о сортировке массива в n ln 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]);
}

Answer 2

Я не понимаю решения Nikitas. Я вижу не «j», а «n». Отсутствует ли внешняя петля?

Для массива из 10 значений он будет иметь 9 отличий, затем 8, 7, 6, ... к 1; право?

Мое решение будет:

int a[] = {9, 3, 5, 2, 7, 4, 6, 8, 0, 1};
// find starting point (3)
int start = 0;
for (; start < a.length -1 && a[start] > a[start+1];)
    ++start;
// find upper bound (8)
int upper = start; 
for (int j = start + 1; j < a.length; ++j)  
{
    if (a[j] > a[upper])
        upper = j;
}
// find lower bound (2)
int lower = start;
for (int l = lower; l < upper; ++l)
{
    if (a[l] < a[lower])
        lower = l;
}
System.out.println ("from:\t" + a[lower] + " to: " + a[upper]);

В прозаах: Вы ищете начальную точку, которая в примере не 9, потому что справа нет большего значения, а 3 есть.

Из 3 вы ищите максимум справа, который равен 8.

Между 3 и 8 наименьшее значение ниже 3 равно 2. Там вы получили максимальный интервал.

Answer 3

Сортировка массива, но отслеживание исходной позиции каждого элемента.Затем просмотрите массив, начиная с обоих концов и двигаясь по направлению к середине, пока не найдете пару, которая изначально была в правильном порядке.