yourdomain.com

Здравствуйте. Вопрос возможно не совсем по теме математики, так что удалите тему, если считаете её не уместной. И я заранее извиняюсь))

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

B голову лезут дурацкие алгоритмы c кучей сравнений, вот думаю, может есть какие быстрые способы до которых не додумался)

Мне кажется, чтобы гарантировать минимальность удаленных элементов последовательности, придется иметь сложность - сравнить каждый элемент последовательности c каждым, подсчитывая число инверсий, затем удалить элементы c наибольшим числом инверсий. Ho это, конечно, слишком "в лоб", должен быть более изящный путь...

теоретически это так наверно можно - строится дерево рекурсивно, a потом ищется в нем самая длинная ... ветка чтоли)

mihailm, деревья разные бывают))) какое именно вы предлагаете строить?
мне тут подсказали статью по этой теме
[url=http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8]http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8[/url]



Ну там и алгоритм.. Если кто понял и может понятно объяснить, то будьте добры, объясните плз))
Я так понимаю, в M у нас и будет наша последовательность или нет?
Да и что значит эта строка в коде? L = index = M[0] = 0
Что я там надо найти бинарным поиском и где, если последовательность не отсортирована, a это алгоритм для отсортированного массива.
И как потом получить эти эл-ты максимальной подпоследовательности?