Give a list of distinct integers>=2. Take any subset of it with size>=2. A subset is called perfect if after arranging the numbers in ascending order. It satisfies a[i]*a[i]=a[i 1] for all elements in the subset. We have to return the size of a perfect subset that is maximum.

My Thoughts:
One naive approach could be to choose an element one by one and see what's the size of the perfect subset it forms, and then we could simply return the max size. This will be computationally intensive.
Any ideas for an elegant solution

CodePudding user response：

This sounds like a variation on the Longest Increasing Subsequence problem.

You can sort the initial sequence (or set) of numbers in ascending order in an array Nums[1..N]. Let L[i] be the size of the largest perfect subset ending with the value at position i (i.e. Nums[i]).

Then L[i] = L[j] 1 if we can find an index j such that Nums[j]^2 = Nums[i]. Otherwise, L[i] = 1. Because Nums is sorted, you can binary search the index j.

This gives an O(N log N) solution.