Gọi F[i] là độ dài dãy con dài nhất thỏa 2 đk sau:
_ đk đề bài
_ dãy con đó kết thúc tại ptử thứ i
Giả sử ta đã tính đc đến F[x-1]. Ta lập công thức tính F[x]
Vì F[x] phải thỏa 2 đk phía tren nên ta phải tìm những thằng trước ptử thứ x và là ước số của ptử thứ x. trong những thằng thỏa đk, ta chỉ cần chọn thằng y có F[y] lớn nhất (có nghĩa F[y] là độ dài của dãy kết thúc tại y, vì y<x và A[y]<A[x] và A[y] là ước của A[x] nên ta thêm ptử A[x] vào cuối dãy con của A[y]) => F[x] = F[y]+1
Code:
begin
readln(n);
for i:=1 to n do read(A[i]);
kq:=0;
for x:=1 to n do
begin
getmax:=0;
for y:=x-1 downto 1 do if (F[y]>getmax) and (F[x] mod F[y] = 0) then getmax:=F[y];
F[x]:=getmax+1;
if F[x]>kq then kq:=F[x];
end;
writeln(kq);
end.