Для решение данной задачи нам понадобится сделать небольшой предподсчет. Вычислим следующую динамику lisl, r — длина максимальной возрастающей подпоследовательности в исходном массиве на отрезке с l по r заканчивающаяся в элементе с индексом r. Сделаем это следующим образом: зафиксируем левую границу l, после чего начнем перебирать правую границу r принимая во внимание факт, что r-й элемент будет последним в данной подпоследовательности. Теперь нужно перебрать предыдущий элемент входящий в данную подпоследовательности j, такой, что , и обновить значение lisl, r = max(lisl, r, lisl, j + 1).
После того как массив lis посчитан, нужно посчитать fk, r — максимальное число элементов, из которого могут состоять возрастающие подпоследовательности длины не менее k на префиксе исходного массива длины r. Пересчет следующим образом: фиксируем k, затем постепенно увеличиваем r. Для фиксированных k и r перебираем j — если на отрезке с k + 1 до j существует возрастающая подпоследовательность длины не менее k, то мы можем обновить значение fk, j следующим образом: fk, j = max(fk, j, fk, r - 1 + lisr, j). Так не забываем про переход вида fk, j = max(fk, j, fk, j - 1).