Блог

Учитывая массив V, нам нужно найти два индекса (i, j), таких что V[j] > V[i] и (j — i) является максимальным.

Подход грубой силы довольно прост, в котором для каждого значения с индексом i (в диапазоне от 1 до n) мы сравниваем значение с индексом j (в диапазоне от i 1 до n). Мы отслеживаем максимум (j-i) на данный момент, чтобы найти окончательный ответ.

Этот подход имеет временную сложность O (n ^ 2). Есть ли у кого-нибудь предложения по улучшению временной сложности?

Вот подход, который позволит решить проблему за линейное время.

1. Вычислить стек S возрастающих позиций, i такой, что min A[1..i-1] > i с помощью простого прямого сканирования по массиву.
2. Выполнить итерацию по списку в обратном направлении.
3. Если текущий элемент больше значения, заданного вершиной стека S: проверьте, есть ли у нас новая запись, и откройте вершину стека.

Быстрая реализация на python:

 def notsurewhattonamethis(A):
    assert(A)
    S = [0]
    for i,v in enumerate(A):
        if v<A[S[-1]]:
            S.append(i)
    best = (-1,-1)
    for i,v in reversed(list(enumerate(A))):
        while v>A[S[-1]]:
            j = S.pop()
            d = i - j
            if d > best[1]-best[0]:
                best = (j,i)
            if not S: return best
    return best
  

Если у вас есть известное ограничение элементов массива (иначе смотрите Обновление ниже) Я могу предложить вам алгоритм с временной сложностью O(n*log(MaxN)) и пространственной сложностью O (maxN), где maxN = Max(V [i]). Для этого алгоритма нам нужна структура, которая может достигать минимума в массиве от 1 до N с временной сложностью O (log(N)) и обновлять элемент массива с временной сложностью O (log(N)). Дерево Фенвика может выполнять эти трюки. Давайте назовем эту структуру минимизатором. Затем нам нужно:

1. Перебрать все элементы в заданном порядке v[i] и поместить в позицию v [i] при значении минимизатора i.
2. Для каждого элемента v [i] найдите минимум, используя минимизатор между 1 и v[i-1] (это минимальный индекс элемента, который меньше v [i])
3. Запомните максимальную разницу между i и найденным минимальным индексом элемента, который меньше v[i].

ОК. Я пытался написать некоторый псевдокод:

 prepare array (map values)
init minimizator

ansI = -1
ansJ = -1

for i from 0 to v.length-1
  minIndexOfElementLessThanCurrent = get min value from 1 to v[i]-1 (inclusive) using minimizator
  set to minimizator v[i] position value i

  if minIndexOfElementLessThanCurrent is exists
    if ansJ - ansI < i - minIndexOfElementLessThanCurrent 
      ansJ = i
      ansI = minIndexOfElementLessThanCurrent
  

Реализация на C :

 class FenwickTree
{
    vector<int> t;
    int n;

public:

    static const int INF = 1000*1000*1000;

    void Init (int n)
    {
        this->n = n;
        t.assign (n, INF);
    }

    int GetMin (int i)
    {
        int res = INF;
        for (; i >= 0; i = (i amp; (i 1)) - 1)
            res = min (res, t[i]);
        return res;
    }

    void Update (int i, int value)
    {
        for (; i < n; i = (i | (i 1)))
            t[i] = min (t[i], value);
    }
};

pair<int, int> Solve(const vector<int>amp; v)
{
    int maxElement = 0;
    for(int i = 0; i < v.size(); i  )
        maxElement = max(maxElement, v[i]);

    FenwickTree minimizator;
    minimizator.Init(maxElement 1);

    int ansI = -1, ansJ = -1;
    for(int i = 0; i < v.size(); i  )
    {
        int minLeftIndex = minimizator.GetMin(v[i]-1);      
        minimizator.Update(v[i], i);

        if(minLeftIndex == FenwickTree::INF) continue; // no left elements less than v[i]

        if(ansJ - ansI < i - minLeftIndex)
        {           
            ansJ = i;
            ansI = minLeftIndex;
        }
    }
    return make_pair(ansI, ansJ);
}
  

Обновить:
Если вид элементов не является int (например, double) или если максимальное значение элементов массива слишком велико (например, 10 ^ 9), мы можем
сопоставьте значения массива (это не повлияет на результат) с целочисленным набором 1 .. N, и тогда временная сложность должна быть O (n * log(n))

Обновить:

Если элементы являются целыми числами — есть O(max(maxN, n)) решение. Итак, если maxN <= n сложность равна O(N). Нам просто нужно ответить на запрос «получить минимум от 1 до N» за постоянное время O (1):

1. Создать массив размером maxN
2. Элемент m[i] массива является минимальным индексом i значения в исходном массиве V.
3. Используя динамическое программирование, создайте массив такого размера, чтобы элемент r[i] массива был минимальным m[j], 1 <= j <= i . Рекуррентное соотношение равно r[i] = min(r[i-1], m[i])

Основная идея этого алгоритма та же, что и выше, только используйте array r для нахождения min от 1 до v[i] .

 C   implementation:

pair<int, int> Solve(const vector<int>amp; v)
{
    int maxElement = 0;
    for(int i = 0; i < v.size(); i  )
        maxElement = max(maxElement, v[i]);

    vector<int> minimum(maxElement   1, v.size()   1);
    for(int i = 0; i < v.size(); i  )
        minimum[v[i]] = min(minimum[v[i]], i); // minimum[i] contains minimum index of element i

    for(int i = 1; i < minimum.size(); i  )
        minimum[i] = min(minimum[i-1], minimum[i]); // now minimum[i] contains minimum index between elements 1 and i

    int ansI = -1, ansJ = -1;
    for(int i = 0; i < v.size(); i  )
    {
        int minLeftIndex = minimum[v[i]-1];      

        if(minLeftIndex >= i) continue; // no left elements less than v[i]

        if(ansJ - ansI < i - minLeftIndex)
        {           
            ansJ = i;
            ansI = minLeftIndex;
        }
    }
    return make_pair(ansI, ansJ);
}
  

Если элементы двойные или что-то еще (очень большие целые числа), мы не можем сопоставить элементы, чтобы установить 1 .. N за линейное время (или можем?). Я знаю только O(n*log(n)) решение (сортировка элементов и т.д.)

Реализация Java выполняется за линейное время.

 public class MaxIndexDifference {

public static void main(String[] args) {
     System.out.println(betweenTwoElements(2, 3, 6, 10, 4));
}

private static int betweenTwoElements(int... nums) {
    int numberOfElements = nums.length;
    int maxDifference = -1, minIndex = 0, maxIndex = 0;

    int[] lMin = new int[numberOfElements];
    int[] rMax = new int[numberOfElements];

    /* Construct lMin such that stores the minimum value (to the left)  from (nums[0], nums[1], ... nums[i])*/

    lMin[0] = nums[0];
    for (int i = 1; i < numberOfElements; i  ) {
        lMin[i] = Math.min(nums[i], lMin[i -1]);
    }
    /* Construct RMax[] such that RMax[j] stores the maximum value (to the right) from (arr[j], arr[j 1], ..arr[n-1]) */
    rMax[numberOfElements - 1] = nums[numberOfElements - 1];
    for (int i = numberOfElements-2; i >= 0; i--) {
        rMax[i] =  Math.max(nums[i], rMax[i   1]);
    }
    /* Traverse both arrays from left to right to find optimum maxIndex - minIndex This process is similar to merge() of MergeSort */
    while (minIndex < numberOfElements amp;amp; maxIndex < numberOfElements) {
        if (lMin[minIndex] < rMax[maxIndex]) {
            maxDifference = Math.max(maxDifference, maxIndex - minIndex);
            maxIndex = maxIndex  1;
        } else {
            minIndex = minIndex  1;
        }           
    }   
    return maxDifference;
}
}
  

Алгоритм с O (N) сложностью:

 #!/usr/bin/perl

use strict;
use warnings;

sub dump_list { print join(", ", map sprintf("-", $_), @_), "n" }

for (0..20) {
    # generate a random list of integers with some convenient bias:
    my @l = (map int(rand(20)   20 - $_), 0..19);

    my $max = $l[-1];
    my $min = $l[0];

    my @max;
    for my $l (reverse @l) {
        $max = $l if $l > $max;
        push @max, $max;
    }
    @max = reverse @max;

    my @min;
    for my $l (@l) {
        $min = $l if $l < $min;
        push @min, $min;
    }

    my $best_i = 0;
    my $best_j = -1;
    my $best   = -1;

    my $j = 0;
    for my $i (0..$#l) {
        while ($j < @l) {
            last unless $max[$j] > $min[$i];
            $j  ;
            if ($j - $i > $best) {
                $best = $j - 1 - $i;
                $best_i = $i;
                $best_j = $j - 1;
            }
        }
    }

    print "list: "; dump_list @l;
    print "idxs: "; dump_list 0..$#l;
    print "best: $best, i: $best_i, j: $best_jnn";
}
  

обновление: в ответ на запрос Nohsib:

Допустим, у вас есть случайный список чисел (a[0], a[1], a[2], a [3] …, a [N-1])

Первый шаг — найти для каждого числа максимум слева в виде mas max[i] = maximum(a[0], a[1], ..., a[i]) и минимум справа min[i] = minimum(a[i], a[i 1], ..., a[N-1]) .

Как только у вас есть эти массивы, найти интервал, в котором a[j] < a[k] он максимизируется k-j , почти тривиально.

Попробуйте выполнить это на бумаге с несколькими случайными списками, и вы легко узнаете логику, стоящую за этим.

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

Первая интерпретация: поиск максимального значения V [j]-V [i] при ограничении, что j > i.
Это то, что это почти нахождение минимального и максимального значений. Но, кроме того, существует также ограничение на индексы. Это само по себе не означает, что идея не может быть использована; для любого выбранного V [i] вам просто нужно максимальное значение по сравнению с V [i 1 .. n], и вам не нужно каждый раз пересчитывать эти максимумы, что приводит к этому алгоритму:

• Вычислить максимальный массив суффиксов в O (n)
• Найти пару (V[i], суффиксmax[i 1]) с максимальной разницей в O (n)

Вторая интерпретация: поиск максимального j-i при ограничении, что V[j] > V[i].
Я не могу придумать ничего хорошего.