Подсчет максимального элемента, присутствующего во всех непрерывных подмассивах

Question

Массив А, состоящий из N положительных целых чисел. Есть N × (N+1)/2 непустые непрерывные подмассивы массива A.

Мы должны подсчитать максимальный элемент, присутствующий во всех непрерывных подмассивах.
Для примера:

1 2 3 
Subarray List : 
[1] 
[2] 
[3] 
[1,2] 
[2,3] 
[1,2,3] 

Maximum Element : 
[1] 
[2] 
[3] 
[2] 
[3] 
[3] 

Мой подход:
Использование Segment Tree запроса Максимальный элемент, присутствующий в интервале

Код:

public static void get_max_freq(int a , int b , ArrayList<Long> freq ,ArrayList<Integer> P , int n , int[] A){ 

     if(a>b) return; 

    int index = query(1,0,n, a, b, A); // Segment Tree O(Logn) 

    long temp = (index-a+1)*(b-index+1); 
    freq.add(temp); 
    P.add(A[index)); 

    get_max_freq(a,index-1, freq, P, n, A); 
    get_max_freq(index+1, b, freq, P,n, A); 

} 

Я интересно мое решение является правильным, если элементы не уникальный в массиве.

Есть ли более быстрое и лучшее решение, чем это.

Answer 1

Я думаю, что вы чрезмерны. Чтобы построить дерево сегментов, вам понадобится пространство O(nlogn), и вы сделаете это в O(n) времени. После этого вам нужно будет ответить на ваши n(n+1)/2 запросы, каждый из которых будет принимать O (logn), поэтому в основном вам это будет стоить O(n^2*logn).

Подход Bruteforce (получить все интервалы и рассчитать максимум на каждом из них) будет работать в O(n) памяти и O(n^3).

Но вы можете рассчитать все максимумы с помощью следующего простого алгоритма. Пусть ваш массив будет [a0, a1, a2, ..., an]. Начните с 0-го элемента и вычислите все их максимумы в диапазоне, начиная с этого элемента: max(a0-a0), max(a0-a1), ... max(a0-an). Вы можете сделать это в O(n), просто потому, что max(ai-an) = max(max(ai-a(n-1)), an) (предыдущий максимальный и текущий элемент). Итак, вы вычисляете значения для a0, затем a1 и т. Д. В O(n^2). Вы можете сохранить их и затем вывести их в нужном формате. Вы закончили с пространством и временем O(n^2) с супер простым алгоритмом.

P.S. Обратите внимание, что вы не можете сделать лучше, чем O(n^2), потому что вам нужно как минимум вывести n*(n+1)/2 элементов, поэтому вы можете только надеяться уменьшить сложность пространства.