Поиск максимальной отсортированной подпоследовательности

Question

Предположим, что нам заданы множество целых чисел целых чисел S = {(x_1, y_1), ..., (x_n, y_n)}. Что является наиболее эффективным способом вычисления максимальной последовательности элементов (a_1, b_1), ..., (a_m, b_m) в S со свойством, что

< a_i = а_ {+ 1}

b_i < = b_ {i + 1}

для i = 1, ..., m-1, т.е. последовательность упорядочена по отношению к обеим компонентам. Я могу придумать с квадратичным алгоритмом, который выполняет следующие действия:

1. Мы сортируем элементы S по отношению к первой координате, давая (c_1, D_1), ..., (C_N, D_N), где c_i < = c_ {i + 1}.

2. Используя динамическое программирование, для каждого (c_i, d_i) мы вычисляем самую длинную последовательность, упорядоченную по отношению к обоим компонентам, которая заканчивается на (c_i, d_i). Это можно сделать в линейном времени, как только мы узнаем самую длинную такую ​​последовательность для (c_1, d_1) ..., (c_ {i + 1}, d_ {i + 1}).

Поскольку мы должны выполнить O (NlogN) вид на шаге 1 и линейный поиск для каждого индекса в шаге 2, который является квадратичным, мы в конечном итоге с квадратичным выполнением.

Я пытался выяснить, существует ли более быстрый, т.е. способ O (nlogn) генерации максимальной последовательности из двух видов множества S: один по отношению к первому компоненту и один по отношению к второй. Это возможно?

Answer 1

Да, это возможно O(n log n).

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

2. Давайте посмотрим на любую отсортированную подпоследовательность этой упорядоченной последовательности. Вторые элементы образуют возрастающую подпоследовательность. Вот почему мы можем найти самую длинную возрастающую подпоследовательность в отсортированной последовательности для второго элемента каждой пары (полностью игнорируя первые элементы, поскольку они уже отсортированы должным образом). Самая длинная возрастающая подпоследовательность для массива чисел может быть найдена в O(n log n) времени (это известная проблема).