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

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

В Википедии есть отдельная статья на эту тему: http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8

Спасибо! Вообще не думал, что там на эту тему статья будет))


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

Это сообщение отредактировал(а) Carlos0N - 16.12.2010, 00:59