# К(N). Таким образом,

К(N). Таким образом, для решения задачи достаточно последовательно вычислить значения К(i) для всех значений i от 1 до N. В силу условия задачи, для вычисления значения К(i+1) достаточно использовать предыдущие значения К(j), j=1,...i, причем только те из них, для которых выполняется условие А[i+1] mod A[j] = 0. Таким образом, К(i+1)=max{ К(j) }+1 j=1,...i, А[i+1] mod A[j] = 0 или равно 1, если (i+1)-й элемент не делится ни на один предыдущий. Для приведенного примера функции К будет соответствовать массив К i 1 2 3 4 5 A 5 -3 6 0 -10 E 1 1 2 3 2 Из матрицы К видно, что максимальная длина подпоследовательности равна 3, при этом последним элементом такой последовательности является 4-й элемент. Для определения номера предпоследнего (а он является последним элементом подпоследовательности, длина которой на единицу меньше максимальной длины), достаточно найти такой индекс j, для которого выполняются соотношения j=1,...i, А[i] mod A[j] = 0 и К[i] - К[j] =1. Зная предыдущий элемент (элемент с индексом 2), аналогичным образом можно найти элемент, стоящий перед ним. Процесс заканчивается тогда, когда будет найден элемент, который является начальным элементом подпоследовательности (для которого значение функции К равно 1). Нетрудно заметить, что элементы подпоследовательности (структура решения) восстанавливается точно в обратном порядке, в котором происходило заполнение матрицы, соответствующей подзадачам решаемой задачи.

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа