Решение задачи 21.
Для решения задачи элементы массива удобно упорядочить по абсолютной величине (в порядке неубывания). Если в массиве есть элементы, равные 0, то один из них и будет последним элементом искомой последовательности, поэтому их можно игнорировать. Пусть К(i) обозначает максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством, последним элементом которой является i-й элемент.
Понятно, что наименьшему по абсолютной величине элементу ничего не может предшествовать ни один элемент, поэтому К(р)=0, где р - индекс первого ненулевого элемента.
Для каждого следующего элемента с номером j, j=р+1,...,N, необходимо определить максимальное количество элементов, которое может предшествовать рассматриваемому элементу, с учетом требуемого свойства. Понятно, что это количество есть максимум из величин К(р1), К(р2),..., К(рm), где элементы с номерами p1,p2,...,pm, р<=p1<p2<...<pm<j являются делителями элемента с номером j. Поэтому мы имеем рекуррентную формулу для вычисления К(j):
К(j) = мах (К(p1),К(p2),...,К(pm)).
Значение К(N), вычисленное по описанному выше правилу, и определяет максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством (без учета возможного нуля в конце последовательности).
Для того, чтобы установить, какие элементы образуют максимальную последовательность, достаточно для каждого номера j помнить тот номер из p1,p2,...,pm, на котором достигается максимум для чисел К(p1),К(p2),...,К(pm). Эти номера можно определять параллельно с вычислением значения К(j) в некотором массиве, например ПРЕДОК. Используя эту информацию, легко определить номера элементов последовательности, проходя от элемента i с максимальным значением К(i) к элементу, который ему предшествует (ПРЕДОК(i)), до тех пор, пока не придем к первому элементу f последовательности (ПРЕДОК(f)=0).
|
