Interview Practice: Leetcode 368. Largest Divisible Subset

Interview Practice: Leetcode 368. Largest Divisible Subset

This question is actually the modified version of "Longest Increasing Subsequence".
For my current number p, I check all the number that's larger than it and keep the max count from the numbers that can be divided by p.

Idea:
(1) Sort the array. Why? This can improve the efficiency. With sorted array, we can just compare the current number with the numbers after it. Otherwise, we need to compare all possible pairs.
(2) Create an array that store the count of numbers it can divide.
(3) Use two for loops. First we start from the largest number and go decreasingly. Second we start from the position of first for loop and go to the end of the array.
(4) For each number i, we check whether it can divide j. If yes, we compare the count in j with the max count we seen before. Keep the largest one.
(5) After compare number i with all number larger than it, we compare the count of i with the global max. If it's larger, keep the max count and the idx of i.
(6) We also keep another information. A map that point to the next number. What's this mean? If we have map i--> j , this means when we start from i, the longest path is go to j.
(7) In the end, we use the maxIdx and path mapping to reconstruct the path.

Read full article from Interview Practice: Leetcode 368. Largest Divisible Subset