Найти максимальную разность между индексами j и i, для которых j> я и a [j]> a [i] в ​​O (n)

Ответ 1

Для краткости я собираюсь предположить, что все элементы уникальны. Алгоритм может быть расширен для обработки неединственного элемента.

Во-первых, обратите внимание, что если x и y являются вашими желаемыми местами max и min соответственно, тогда не может быть никаких a[i] > a[x] и i > x, и аналогично, no a[j] < a[y] и j < y.

Итак, мы сканируем массив a и построим массив S, так что S[i] содержит индекс минимального элемента в a[0:i]. Аналогично массив T, который содержит индекс максимального элемента в a[n-1:i] (т.е. Назад).

Теперь мы можем видеть, что a[S[i]] и a[T[i]] обязательно уменьшают последовательности, поскольку они были минимальными до i и максимумом от n до i соответственно.

Итак, теперь мы пытаемся выполнить процедуру сортировки типа слияния. На каждом шаге, если a[S[head]] < a[T[head]], мы выталкиваем элемент из T, иначе мы вытаскиваем элемент из S. На каждом таком этапе записываем разницу в голове S и T, если a[S[head]] < a[T[head]]. Максимальное такое различие дает вам свой ответ.

EDIT: Вот простой код в Python, реализующий алгоритм.

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist

Ответ 2

Пусть сделаем это простое наблюдение: если мы имеем 2 элемента a [i], a [j] с я < j и a [i] a [j], тогда мы можем быть уверены, что j не будет частью решения в качестве первого элемента (он может быть вторым, но вторым), потому что я был бы лучшей альтернативой.

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

Например, для: 12 3 61 23 51 2 жадно уменьшающаяся последовательность построена следующим образом:

12 → 12 3 → игнорируем 61, потому что он хуже 3 → игнорируем 23, потому что он хуже 3 → игнорируем 51, потому что он хуже 3 → 12 3 2.

Таким образом, ответ будет содержать на левой стороне 12 3 или 2.

Теперь в случайном случае это имеет длину O (log N), поэтому вы можете бинарный поиск на нем для каждого элемента в качестве правой части ответа, и вы получите O (N log log N), что хорошо, и если вы применяете ту же логику в правой части строки в случайном случае, вы можете получить O (log ^ 2 N + N (из чтения)), который является O (N). Но мы также можем делать O (N) в неслучайном случае.

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

1) Если мы нашли лучшее решение, взяв последнюю из уменьшающейся последовательности и текущее число, чем обновляем ответ

2) Даже если мы обновим ответ или нет, мы выставим последний элемент уменьшающейся последовательности, потому что мы это идеальное соответствие (любое другое совпадение будет слева и даст ответ с меньшим j - i)

3) Повторяем, пока мы можем соединить эти 2

Пример кода:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    // let solve the problem
    vector<int> decreasing; 

    pair<int, int> answer;

    // build the decreasing sequence
    decreasing.push_back(1);
    for (int i = 1; i <= N; ++i)
        if (A[i] < A[decreasing.back()])
            decreasing.push_back(i); // we work with indexes because we might have equal values

    for (int i = N; i > 0; --i) {
        while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
            pair<int, int> current_pair(decreasing.back(), i);
            if (current_pair.second - current_pair.first > answer.second - answer.first)
                answer = current_pair;
            decreasing.pop_back();
        }
    }

    cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")\n";
}

Позднее Редактировать: Я вижу, что вы привели пример: я проиндексировал из 1, чтобы сделать его более ясным, и я печатаю (i, j) вместо (j, i). Вы можете изменить его по своему усмотрению.

Ответ 3

Чтобы решить эту проблему, нам нужно получить два оптимальных индекса arr []: левый индекс я и правый индекс j. Для элемента arr [i] нет необходимости рассматривать arr [i] для левого индекса, если в левой части arr [i] есть элемент, меньший, чем arr [i]. Аналогично, если в правой части arr [j] имеется больший элемент, то нам не нужно рассматривать этот j для индекса справа. Итак, мы построим два вспомогательных массива LMin [] и RMax [] такие, что LMin [i] содержит наименьший элемент в левой части arr [i], включая arr [i], а RMax [j] содержит наибольший элемент в правой части arr [j], включая arr [j]. После построения этих двух вспомогательных массивов мы перемещаем обе эти массивы слева направо. Если мы пересекаем LMin [] и RMa [], если мы видим, что LMin [i] больше RMax [j], то мы должны двигаться вперед в LMin [] (или do я ++), потому что все элементы слева от LMin [i] больше или равно LMin [i]. В противном случае мы должны двигаться вперед в RMax [j], чтобы искать большее значение j - i. Вот код c, выполняющийся в O (n) времени:

#include <stdio.h>
#include <stdlib.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Ответ 4

Мы можем избежать проверки всего массива, начиная с максимальной разницы ji и сравнивая arr[j]>arr[i] для всех возможных комбинаций j и я для этой конкретной максимальной разности всякий раз, когда мы получаем комбинацию (j,i) с помощью arr[j]>arr[i] мы можем выйти из цикла

Пример: в массиве {2,3,4,5,8,1} первый код проверяет максимальную разницу 5(5-0) т. (arr[0],arr[5]), если arr[5]>arr[0] Функция arr[5]>arr[0] выйдет, иначе примут комбинации max diff 4 (5,1) and (4,0) ie arr[5],arr[1] and arr[4],arr[0]

int maxIndexDiff(int arr[], int n)
{
    int maxDiff = n-1;
    int i, j;

    while (maxDiff>0)
            {
            j=n-1;
            while(j>=maxDiff)
            {
            i=j-maxDiff;
            if(arr[j]>arr[i])
            { 
            return maxDiff;  
            }
            j=j-1;
            }
            maxDiff=maxDiff-1;
            }
         return -1;  
    }'

https://ide.geeksforgeeks.org/cjCW3wXjcj

Ответ 5

Вот очень простая реализация O (n) Python объединенной идеи с последующей последовательностью. Реализация работает даже в случае повторяющихся значений:

downs = [0]
for i in range(N):
    if ar[i] < ar[downs[-1]]:
        downs.append(i)

best = 0
i, j = len(downs)-1, N-1
while i >= 0:
    if ar[downs[i]] <= ar[j]:
        best = max(best, j-downs[i])
        i -= 1
    else:
        j -= 1
print best

Ответ 6

Я могу думать о совершенствовании над O (n ^ 2), но нужно проверить, является ли это O (n) в худшем случае или нет.

• Создайте переменную BestSoln=0; и перемещайте массив для первого элемента и сохранить наилучшее решение для первого элемента i.e bestSoln=k;.
• Теперь для второго элемента рассмотрим только элементы, которые k удалены от второго элемента.
• Если BestSol n в этом случае лучше первой итерации, тогда замените иначе это будет так. Продолжайте итерацию для других элементов.

Это можно улучшить, если мы сохраним максимальный элемент для каждого подмассива, начиная с i до конца. Это можно сделать в O (n), пройдя массив от конца. Если конкретный элемент больше локального max, тогда нет необходимости делать оценку для этого элемента.

Вход:

{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

создать локальный массив max для этого массива:

[18,18,18,18,18,18,18,0,0] O(n).

Теперь перейдите к массиву для 9, здесь лучшим решением будет i=0,j=8.  Теперь для второго элемента или после него нам не нужно оценивать. и наилучшим решением является i=0,j=8.

Но предположим, что array - Input:

{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}

Локальный максимальный массив [18,18,18,18,18,18,18,0,0], то на первой итерации нам не нужно оценивать, как локальный максимум меньше текущего элемента.

Теперь для второй итерации лучшим решением является i=1,j=10. Теперь для других элементов нам не нужно рассматривать оценку, поскольку они не могут дать лучшее решение.

Позвольте мне узнать ваше мнение о вашем случае использования, к которому мое решение не применимо.

Ответ 7

Это очень простое решение для O (2n) скорости и дополнительного ~ O (2n) пространства (в дополнение к входному массиву). Следующая реализация выполняется в C:

int findMaxDiff(int array[], int size) {

    int index = 0;
    int maxima[size];
    int indexes[size];

    while (index < size) {
        int max = array[index];
        int i;
        for (i = index; i < size; i++) {
            if (array[i] > max) {
                max = array[i];
                indexes[index] = i;
            }
        }
        maxima[index] = max;
        index++;
    }

    int j;
    int result;
    for (j = 0; j < size; j++) {
        int max2 = 0;
        if (maxima[j] - array[j] > max2) {
            max2 = maxima[j] - array[j];
            result = indexes[j];
        }
    }

    return result;
}

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

Ответ 8

Мое решение с помощью O (log n) (Пожалуйста, исправьте меня здесь, если я ошибаюсь при вычислении этой сложности) время...

Идея заключается в том, чтобы вставить в BST, а затем выполнить поиск node, и если node имеет правильный дочерний элемент, то перейдите через правое вспомогательное дерево, чтобы вычислить node с максимальным индексом.

    import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t1 = Integer.parseInt(br.readLine());
        for(int j=0;j<t1;j++){
            int size = Integer.parseInt(br.readLine());
            String input = br.readLine();
            String[] t = input.split(" ");
            Node root = new Node(Integer.parseInt(t[0]),0);
            for(int i=1;i<size;i++){
                Node addNode = new Node(Integer.parseInt(t[i]),i);
                insertIntoBST(root,addNode);                
            }
            for(String s: t){
                Node nd = findNode(root,Integer.parseInt(s));
                if(nd.right != null){
                    int i = nd.index;
                    int j1 = calculate(nd.right);
                    mVal = max(mVal,j1-i);
                }

            }

            System.out.println(mVal);
            mVal=0;
        }
    }

    static int mVal =0;

    public static int calculate (Node root){
        if(root==null){
            return -1;
        }
        int i = max(calculate(root.left),calculate(root.right));
        return max(root.index,i);
    }

    public static Node findNode(Node root,int n){
        if(root==null){
            return null;
        }
        if(root.value == n){
            return root;
        }
        Node result = findNode(root.left,n);
        if(result ==null){
            result = findNode(root.right,n);   
        }
        return result;
    }

    public static int max(int a , int b){
        return a<b?b:a;
    }

    public static class Node{
        Node left;
        Node right;
        int value;
        int index;

        public Node(int value,int index){
            this.value = value;
            this.index = index;
        }
    }

    public static void insertIntoBST(Node root, Node addNode){

        if(root.value< addNode.value){
            if(root.right!=null){
                insertIntoBST(root.right,addNode);              
            }else{
                root.right = addNode;
            }
        }
        if(root.value>=addNode.value){
            if(root.left!=null){
                insertIntoBST(root.left,addNode);               
            }else{
                root.left =addNode;
            }
        }
    }


}

Ответ 9

Упрощенный алгоритм ответа Subhasis Das:

# assume list is not empty
max_dist = 0
acceptable_min = (0, arr[0])
acceptable_max = (0, arr[0])
min = (0, arr[0])

for i in range(len(arr)):
  if arr[i] < min[1]:
    min = (i, arr[i])
  elif arr[i] - min[1] > max_dist:
    max_dist = arr[i] - min[1]
    acceptable_min = min
    acceptable_max = (i, arr[i])

# acceptable_min[0] is the i
# acceptable_max[0] is the j
# max_dist is the max difference

Ответ 10

Упрощенная версия Subhasis Das отвечает с использованием вспомогательных массивов.

def maxdistance(nums):
    n = len(nums)
    minima ,maxima = [None]*n, [None]*n
    minima[0],maxima[n-1] = nums[0],nums[n-1]
    for i in range(1,n):
        minima[i] = min(nums[i],minima[i-1])
    for i in range(n-2,-1,-1):
        maxima[i]= max(nums[i],maxima[i+1])

    i,j,maxdist = 0,0,-1
    while(i<n and j<n):
        if minima[i] <maxima[j]:
            maxdist = max(j-i,maxdist)
            j = j+1
        else:
            i += 1
    print maxdist

Ответ 11

Ниже приведено решение C++ для условия a[i] <= a[j]. Требуется небольшая модификация для обработки случая a[i] < a[j].

template<typename T>
std::size_t max_dist_sorted_pair(const std::vector<T>& seq)
{
    const auto n = seq.size();
    const auto less = [&seq](std::size_t i, std::size_t j)
        { return seq[i] < seq[j]; };

    // max_right[i] is the position of the rightmost
    // largest element in the suffix seq[i..]
    std::vector<std::size_t> max_right(n);

    max_right.back() = n - 1;
    for (auto i = n - 1; i > 0; --i)
        max_right[i - 1] = std::max(max_right[i], i - 1, less);

    std::size_t max_dist = 0;
    for (std::size_t i = 0, j = 0; i < n; ++i)
        while (!less(max_right[j], i))
        {
            j = max_right[j];
            max_dist = std::max(max_dist, j - i);
            if (++j == n)
                return max_dist;
        }

    return max_dist;
}

Ответ 12

Я решил этот вопрос здесь.

https://github.com/nagendra547/coding-practice/blob/master/src/arrays/FindMaxIndexDifference.java

Вводить код здесь тоже. Благодарю.

private static int findMaxIndexDifferenceOptimal(int[] a) {

        int n = a.length;
        // array containing minimums
        int A[] = new int[n];
        A[0] = a[0];
        for (int i = 1; i < n; i++) {
            A[i] = Math.min(a[i], A[i - 1]);
        }

        // array containing maximums
        int B[] = new int[n];
        B[n - 1] = a[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            B[j] = Math.max(a[j], B[j + 1]);
        }

        int i = 0, maxDiff = -1;
        int j = 0;
        while (i < n && j < n) {
            if (B[j] > A[i]) {
                maxDiff = Math.max(j - i, maxDiff);
                j++;
            } else {
                i++;
            }

        }

        return maxDiff;
    }

Ответ 13

Метод 1 (простой, но неэффективный)

Запустите две петли. Во внешнем цикле выбирайте элементы по одному слева. Во внутреннем цикле сравните выбранный элемент с элементами, начиная с правой стороны. Остановите внутренний цикл, когда вы увидите элемент, который больше, чем выбранный элемент, и продолжайте обновлять максимальный j-i до сих пор.

#include <stdio.h>
/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff = -1;
    int i, j;

    for (i = 0; i < n; ++i)
    {
        for (j = n-1; j > i; --j)
        {
            if(arr[j] > arr[i] && maxDiff < (j - i))
                maxDiff = j - i;
        }
    }

    return maxDiff;
}

int main()
{
    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Сложность времени: O (n ^ 2)

Метод 2 (эффективный)

Чтобы решить эту проблему, нам нужно получить два оптимальных индекса arr []: левый индекс я и правый индекс j. Для элемента arr [i] нам не нужно рассматривать arr [i] для левого индекса, если в левой части arr [i] есть элемент, меньший, чем arr [i].
Аналогично, если в правой части arr [j] имеется больший элемент, то нам не нужно рассматривать этот j для индекса справа. Итак, мы построим два вспомогательных массива LMin [] и RMax [] такие, что LMin [i] содержит наименьший элемент в левой части arr [i], включая arr [i], а RMax [j] содержит наибольший элемент в правой части arr [j], включая arr [j].
После построения этих двух вспомогательных массивов мы перемещаем обе эти массивы слева направо. Если мы пересекаем LMin [] и RMa [], если мы видим, что LMin [i] больше RMax [j], то мы должны двигаться вперед в LMin [] (или do я ++), потому что все элементы слева от LMin [i] больше или равно LMin [i]. В противном случае мы должны двигаться вперед в RMax [j], чтобы искать большее значение j-i.

#include <stdio.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}

Сложность времени: O (n)
Вспомогательное пространство: O (n)
Источник geeksforgeeks