Divisible Set

In this approach, we can see that for every element, we choose to either pick it or not pick it. An element can only be picked when it satisfies the condition in the question.

So, before picking any element, we need to check if either of the above two conditions satisfies each element already present in the current subset. But there's an important observation that allows us to optimise the above checking process. If the largest number in the subset formed till now divides the next element to be chosen, then every other element in the subset will divide it (because the subset formed till now follows the above conditions).

We create getMaxSubset(arr, start), where ‘start’ is the index of the current element to be inserted in the subset or not in the array ‘arr’. 

Algorithm:

• In the function getMaxSubset(arr, start)
  • If start is not less than the length of arr, return an empty array
  • Create an empty array subSet
  • Iterate i from the start + 1 to the size of arr
    • If arr[i] % arr[start] equals 0, continue the loop
    • Set res as getMaxSubset(arr, i)
    • If the size of the res is not less than the size of ans set subSet as res
  • Insert arr[start] in subSet and return it.
• In the given function
  • Sort the arr array
  • Create an empty array subSet
  • Iterate i from 0 to the size of arr
    • If arr[i] % arr[start] not equals 0, continue the loop
    • Set res as getMaxSubset(arr, i)
    • If the size of the res is not less than the size of ans set subSet as res
  • Return subSet

In this approach, we will try to memoize the previous approach as we can find that there are lots of repeated function calls and redundant calculations. We can avoid these unnecessary calculations by memoizing the results and reusing them in future calls. 

Here, we use ‘cache’ to store the largest subset starting with ith index element. Once ‘cache’[i] is calculated, its result can be reused in future calls again instead of recalculating it.

We create getMaxSubset(arr, start, cache), where ‘start’ is the index of the current element to be inserted in the subset or not in the array ‘arr’ and cache is the cache to store the subsets starting at each index.

Algorithm:

• In the function getMaxSubset(arr, start, cache)
  • If start is not less than the length of arr return an empty array
  • If cache[start] is not empty return cache[cache]
  • Iterate i from start + 1 to the size of arr
    • If arr[i] % arr[start] equals 0, continue the loop
    • Set res as getMaxSubset(arr, i, cache)
    • If the size of the res is not less than the size of the cache[start], set cache[i] as res
  • Insert arr[start] in cache[start] and return it.
• In the given function
  • Sort the arr array
  • Create an array of empty array of size equal to arr called ‘cache.’
  • Create an empty array subSet
  • Iterate i from 0 to the size of arr
    • If arr[i] % arr[start] equals 0, continue the loop
    • Set res as getMaxSubset(arr, i, cache)
    • If the size of the res is not less than the size of subSet set subSet as res
  • Return subSet

In this approach, the logic is similar to what's used in the previous approach, with the only change being that we are doing it from the bottom-up iteratively. We will create a ‘dp’ table to store the solutions for the previous approaches, where ‘dp’[i] is the largest subset starting at ith index.

Instead of explicitly generating the largest subset for every index, we can find only the size of the largest subset starting at ith index and then try to reconstruct it.

To reconstruct the largest subset, we can keep track of the successor element that leads to the largest subset starting at index ‘i’.

Algorithm:

• Sort the arr array, and set ‘n’ as the size of ‘arr’, set ‘maxInd’ as 0
• Create two array ‘dp’ and pred of size ‘n’. initialise all the elements of ‘dp’ with 1 and ‘pred’ with -1
• Create an empty array 'ans'.
• Iterate ‘i’ from 1 to ‘n’ - 1
  • Iterate ‘j’ from 0 to ‘i’ - 1
    • If ‘arr’[i] % ‘arr’[j] == 0 and ‘dp’[i] < ‘dp'[j]+1
      • Set 'dp'[i] as 'dp'[i] + 1, and 'pred'[i] as j
  • Else ‘dp’[i] is greater than ‘dp’[maxInd], set ‘maxInd’ as i
• While ‘maxInd' is not equal less than 0
  • Insert ‘arr’[maxInd] in ans
  • Set ‘maxInd’ as ‘pred’[maxInd]
• Return 'ans'