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

Ответ 1

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

#!/usr/bin/perl

use strict;
use warnings;

sub dump_list { print join(", ", map sprintf("%2d", $_), @_), "\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_j\n\n";
}

update: в ответ на запрос 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, почти тривиален.

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

Ответ 2

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

• Вычислить стек S возрастающих позиций i таким образом, чтобы min A[1..i-1] > i с простым просмотром вперед по массиву.
• Перейдите по списку назад.
• В то время как текущий элемент больше, чем значение, заданное вершиной стека 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

Ответ 3

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

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

Ok. Я попытался написать несколько псевдокодов:

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

Реализация С++:

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 & (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>& 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);
}

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

UPDATE:

Если элементы целые - существует решение O(max(maxN, n)). Поэтому, если maxN <= n сложность O (N). Нам просто нужно ответить за запрос "получить минимум от 1 до N" в const time O (1):

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

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

C++ implementation:

pair<int, int> Solve(const vector<int>& 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)) (элементы сортировки и т.д.)

Ответ 4

Реализация 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 && maxIndex < numberOfElements) {
        if (lMin[minIndex] < rMax[maxIndex]) {
            maxDifference = Math.max(maxDifference, maxIndex - minIndex);
            maxIndex = maxIndex +1;
        } else {
            minIndex = minIndex +1;
        }           
    }   
    return maxDifference;
}
}

Ответ 5

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

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

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

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