VPF::Рекурсивный поиск LIS - Форум программистов

Symbolist

Дата 25.2.2011, 01:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.2.2010

Репутация: нет
Всего: нет

Необходимо реализовать рекурсивный поиск максимальной возрастающей подпоследовательности (LIS) в массиве.
Причем в ходе рекурсии необходимо найти не только длину LIS, но и LIS для каждого элемента в массиве.

На данный момент имею только рекурсивную реализацию для нахождения длины LIS:

Код


vector<int> sequence;

/*...*/

int LIS(int prev, int index) {
    if (index == sequence.size() - 1) {
        return 0;
    } else {
        int max = LIS(prev, index + 1);
        if (sequence[index + 1] > prev) {
            int L = 1 + LIS(sequence[index + 1], index + 1);
            if (L > max)
                max = L;
        }
        return max;
    }
    
}

Использую:

Код


int length = LIS(INT_MIN, I);

Итеративные алгоритмы, увы, использовать не положено.
Как грамотно прикрутить сохранение LIS для каждого элемента последовательности к рекурсии?

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »