Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Рекурсивный поиск LIS

Автор: Symbolist 25.2.2011, 01:26

Необходимо реализовать рекурсивный поиск максимальной возрастающей подпоследовательности (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 для каждого элемента последовательности к рекурсии?