Here's the observation: if you sort the array, then for any chain where each divides the next, you only need to check adjacent pairs. Why? If divides and divides , then divides . Divisibility is transitive.
So after sorting, this becomes LIS where the condition is "divides" instead of "less than". = length of longest divisible chain ending at index . The formula: for all where .