Объясните алгоритм для решения проблемы «наибольшая возрастающая подпоследовательность»

Question

Я пытался понять этот алгоритм в течение последних двух часов, но, похоже, не могу его понять.Может ли кто-нибудь объяснить это в понятной форме?

function lis_length(a)
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

Answer 1

После завершения первого (двойного) цикла q[i] - это длина самой длинной увеличивающейся подпоследовательности, заканчивающейся в позиции i.

Чтобы увидеть, как работает двойной цикл, предположим, что q[j] уже содержитдлина наибольшей увеличивающейся подпоследовательности, заканчивающейся в позиции j, но только для j между 0 и k-1.Учитывая это, как бы вы вычислили q[k]?

Ну, вы бы нашли все j с j < k и a[j] < a[k], посмотрите, какое из соответствующих значений q[j] было наибольшим, добавьтеодин и спрятать это значение в q[k].Это именно то, что делает внутренний цикл.

Поэтому при входе во внутренний цикл q[j] уже имеет правильные значения для j в диапазоне от 0 до k-1.И на выходе, он также имеет правильное значение для k.Таким образом, к моменту выхода из двойного цикла, q[i] имеет правильное значение для всех i между 0 и n.

Последний цикл просто выбирает самый большой из них, что является ответом.

Answer 2

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

Алгоритм принимает массив положительных чисел (не может иметь ноль или меньше в качестве элемента).