У меня есть последовательность целых чисел {a1,a2...an}, и я хочу разделить ее на минимальное количество "возрастающих подпоследовательностей". Например: пусть последовательность будет {10,30,20,40}, тогда ответ будет 2. В этом случае первая возрастающая последовательность будет {10,30,40}, а вторая будет {20}. Я могу сделать это, используя алгоритм O (N ^ 2), но меня особенно интересует решение O (N * log N), которое может служить цели.
Минимальное количество возрастающих подпоследовательностей
comment
какое условие разделения последовательности? Я не понимаю, почему {10,30,20,40} нужно разделить именно на это, а не на что-то другое
- person lenz schedule 10.06.2013
comment
Разве минимальное число не равно нулю? Если не отсортировано.
- person Novak schedule 10.06.2013
comment
Мне жаль. Я пропустил самое важное слово - увеличение. Я отредактировал вопрос. Это исправлено сейчас.
- person divanshu schedule 10.06.2013
Ответы (1)
Это можно сделать с помощью простого жадного алгоритма.
Сохранить отсортированный массив подпоследовательностей, найденных до сих пор. Отсортировано в порядке убывания по значению последнего целого числа в каждой последовательности. Изначально пустой.
Получить первый еще не обработанный элемент из последовательности и найти подпоследовательность, в которой последнее целое число меньше этого элемента, но больше (или равно), чем во всех таких подпоследовательностях. Используйте здесь двоичный поиск, чтобы получить общую сложность O (N log N). Если такой подпоследовательности не найдено, добавьте новую в конец массива. Добавьте этот элемент в эту подпоследовательность. Повторяйте, пока в последовательности есть еще не обработанные элементы.
person
Evgeny Kluev
schedule
10.06.2013
Отсортированный массив подпоследовательностей? Я полагаю, что в худшем случае таких подпоследовательностей может быть 2 ^ n?
- person divanshu; 10.06.2013
@divanshu: нет, в худшем случае есть ровно N подпоследовательностей длиной 1 каждая (когда исходная последовательность отсортирована в порядке убывания).
- person Evgeny Kluev; 10.06.2013
+1: возможно, стоит добавить, что эта проблема известна как сортировка терпения.
- person Peter de Rivaz; 10.06.2013
Спасибо @PeterdeRivaz! Ваш термин «Сортировка терпения» очень помог.
- person divanshu; 10.06.2013
