Подпоследовательность

[shukshin]

Добрый день, уважаемые участники форума!
Задачка:
В заданной последовательности целых чисел найти максимально длинную подпоследовательность чисел такую,
что каждый последующий элемент подпоследовательности делился нацело на предыдущий.
Решение нашел, но (по-моему) перемудрил и у него неважная асимптотика.
В цикле по элементам массива решил строить деревья с $j$-м элементом в виде корня.
Строю так:
Смотрю после $j$-го элемента кратные ему, добавляю в потомки.
Для каждого потомка делаю то же самое.
Далее решаю задачу о максимальной длине от корня до листа в дереве.
Запоминаю полученное значение.
Для полученной длины $l$, можно уйти из основного цикла на $n-l $ шаге.
Возможно, что я упускаю из вида какой-то очевидный алгоритм? Жду ваших советов!

[rockclimber]

shukshin в сообщении #1116564 писал(а):

В цикле по элементам массива решил строить деревья с $j$-м элементом в виде корня.

А деревья-то зачем? Запоминаете в одной переменной начало подпоследовательности, в другой - длину. Если найдется подпоследовательность длиннее, перезаписываете.

[shukshin]

rockclimber, как вы себе это представляете?
для $j$-го элемента (начала подпоследовательности для рассмотрения) последующие элементы могут идти не подряд вплотную.
да и порядок по возрастанию значений никто не обещал. единственное условие для подпоследовательности - возрастание по индексам.
как вы предлагаете грамотно перебирать все возможные подпоследовательности с началом в $j$-м элементе?

[12d3]

Задачка на динамическое программирование. Пусть $a_n$ - наш массив элементов, заведем еще два массива $l_n$ - максимальная длина подпоследовательности, оканчивающейся на данном элементе и $p_n$ - индекс предыдущего элемента в такой подпоследовательности.
В псевдокоде примерно так выглядит.

for i=1 to n:
    l[i] = 1
    p[i] = 0
    for k=1 to i-1:
        if a[k] divides a[i] and l[k] + 1 > l[i]:
              l[i] = l[k]+1
              p[i] = k

Осталось только найти элемент с максимальным $l_i$ и построить подпоследовательность(в обратном порядке), переходя от $i$-го элемента к $p_i$-му. Ну и развернуть получившуюся подпоследовательность.

[shukshin]

12d3, спасибо!

[Dmitriy Blokhin]

Действительно, задача ведь решается тем способом, что написал rockclimber.
Пусть $L_{max}$ - длина максимальной подпоследовательности, $P_{max}$ - индекс, откуда начинается максимальная подпоследовательность.
Пусть $L_{tmp}$ - длина текущей подпоследовательности, $P_{tmp}$ - индекс начала текущей подпоследовательности.
Проходим по массиву, проверяя делимость следующего элемента на текущий. Если делится, увеличиваем $L_{tmp}$, если нет - значит, мы в конце подпоследовательности и если $L_{tmp} > L_{max}$, то присваиваем $L_{max} = L_{tmp}$.

Таким образом, за $O(n)$ мы получим $P_{max}$.

12d3, не могу вникнуть в Ваше решение. Зачем увеличивать $l_i$, если $k$-тый делит $i$-того при том, что $(k + 1) \neq i$. Вы, наверное, подумали, что каждый элемент подпоследовательности должен делить все последующие? Но если так, то, кажется, тоже что-то не то..

[12d3]

Видимо, я условие понял не так. Я считал, что подпоследовательность не обязательно содержит только идущие подряд элементы.

[Dmitriy Blokhin]

Спасибо за ответ, тогда вы предложили решение гораздо более сложной задачи.

[venco]

Подпоследовательность допускает пропуски элементов.

[petrov_ich]

shukshin в сообщении #1116593 писал(а):

rockclimber, как вы себе это представляете?
для $j$-го элемента (начала подпоследовательности для рассмотрения) последующие элементы могут идти не подряд вплотную.

Как это? И что там будет в промежутках?

Цитата:

да и порядок по возрастанию значений никто не обещал. единственное условие для подпоследовательности - возрастание по индексам.

Меньшее число не может поделиться нацело на большее, только и всего.

[venco]

petrov_ich в сообщении #1145207 писал(а):

shukshin в сообщении #1116593 писал(а):

rockclimber, как вы себе это представляете?
для $j$-го элемента (начала подпоследовательности для рассмотрения) последующие элементы могут идти не подряд вплотную.

Как это? И что там будет в промежутках?

Что угодно. Подпоследовательность - любое подмножество элементов в том же порядке, что и в исходной последовательности.
{ 123, 2, 234, 445 } - подпоследовательность последовательности
{ 1, 3, 123, 23424, 2, 333, 99, 234, 445, 1233 }