Maxima подсчет

Question

A = {4, 1, 3, 2}

Существует 10 смежных подматриц. Позвольте мне рассмотреть максимум всех этих подматриц.

Sub array Max 

{4}   4 
{1}   1 
{3}   3 
{2}   2 
{4, 1}   4 
{1, 3}   3 
{3, 2}   3 
{4, 1, 3}  4 
{1, 3, 2}  3 
{4, 1, 3, 2} 4 

Итак:

Max # Occurrences 
1   1 
2   1 
3   4 
4   4 

Вопрос: Есть ли способ для подсчета количества таких случаев в O(n) время? Используя dequeue, я могу найти максимум для всех интервалов, но это займет O(n^2 log n) времени, что невозможно для массива большого размера.

Answer 1

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

Например, с вашего массива, вы получите первый заметить, что 4 является максимумом массива, то, следовательно, максимум всех вложенных массивов, начиная с или до 0 и заканчивая или после 0, то есть 4. Затем вы получаете предыдущие и удаленные подмассивы {} и {1, 3, 2}. Затем вы продолжаете проверять {1, 3, 2} (мы пропускаем пустую, так как это тривиально) 3 - это максимум, и это максимум всех подмассивов, в которых он находится, а именно те, которые начинаются с 1 и заканчиваются 1, там четыре таких (2*2), то он продолжается с подмассивами {1} и {2}.

Необходимо учитывать также сложность, при которой мы сталкиваемся с несколькими максимами. Например, если мы находимся в массиве {1, 4, 3, 4, 3, 2}, вы найдете две максимы (две четверки), то же самое относится и к первому 4 для всех интервалов, где он принадлежит (который здесь 10), а второй максимум - 12, но будьте осторожны, что некоторые из этих интервалов одинаковы, вы должны решить, как их подсчитать (см. ниже). Теперь то же самое относится и к другим числам, которые могут быть только максимумами в подмассиве, где 4 не находится, поэтому мы получаем 3 подматрицы, а именно {1}, {3} и {3, 2}.

Когда у вас есть несколько максимов в промежутке, это не будет так же, как не-ambiguos, как вы хотите их подсчитать. Например, в интервале {4, 3, 4}4 является максимальным в интервале {4} (первый), {4} (второй), {4, 3}, {3, 4} и {4, 3, 4}. Все, кроме последних, довольно прямолинейны, есть один, но как вы хотите считать последнее? Ну, это один интервал, поэтому он один, но вы также можете посчитать его дважды. При анализе массива в соответствии с алгоритмом вы попадете в первую очередь с интервалом 3, а второй - с 3 интервалами, который добавляет до 6, что соответствует случаю, когда вы считаете последний интервал дважды (потому что он имеет два 4 s).

Если вы с другой стороны хотите подсчитать интервал только один раз, вы можете, например, использовать подмассивы для их подсчета. Сначала вы строите максимальный интервал, содержащий каждый из них, и тот, который содержит оба.Например, в массиве {1, 4, 3, 4, 3, 2} у вас есть первые подмассивы, начинающиеся до или в начале 4 и заканчивающиеся в первый или после первого 4, но до второго (это означает, что вы получаете интервал 4), тогда вы соответствуете второму, что означает интервалы, начинающиеся с или до второго 4, но после первого и заканчивающиеся на или после второго 4 (это означает, что вы получаете 6 интервалов), наконец вы считаете их, содержащими оба интервала, который начинается с или до первого 4 и заканчивается на или после второго (это дает 6 интервалов). Когда мы суммируем это, мы заканчиваем 16 интервалами.

Другим решением может быть выбор одного из 4 s, который считается максимальным, а затем обрабатывает оставшиеся 4 s в соответствующем подмассиве. В этом примере можно было бы выбрать второй, потому что это самый средний 4. Это приведет к подсчету 12 интервалов, а затем, когда вы будете обрабатывать левый поднабор ({1, 4, 3}), вы обнаружите, что 4 - это максимум в 4 интервалов. Это также добавит до 16 интервалов, где 4 является максимальным.

Алгоритм делает это в O(N log N) времени в среднем и в O(N^2) времени в худшем случае, если вы используете наивный подход к поиску максимума в подмассивах (то есть O(N)). Однако с использованием segment trees вы должны иметь возможность уменьшить обнаружение максимумов в подмассиве до операции O(log N) после (однократной) конструкции дерева сегмента (то есть O(N)). После построения дерева сегментов наихудший случай будет O(N log N) и в среднем O((log N)^2). В худшем случае подсчет доминирует над сложностью, так что это O(N log N), и в среднем здание дерева сегментов доминирует, поэтому O(N).