LeetCode June Challenge - Day 13

Problem: LeetCode June Challenge - Day 13

Ideas:

  1. Sort the vector so you only need to look after the current element to find multiples.
  2. If we look at the problem as a graph, we are looking for the element with the greatest depth (directed and acyclic graph).

Solution:

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return nums;

        sort(nums.begin(), nums.end());

        vector<int> height(n, 0);
        vector<int> parent(n, -1);
        pair<int,int> best = {0,0};

        for(int i=0; i<n; ++i)
            for(int j=i+1; j<n; ++j)
                if(nums[j] % nums[i] == 0 && height[i] + 1 > height[j]){
                    height[j] = height[i]+1;
                    parent[j] = i;
                    if(height[j] > best.first)
                        best = {height[j], j};
                }

        vector<int> ans;
        int index = best.second;
        while(true){
            ans.push_back(nums[index]);
            if(parent[index] == -1) break;
            index = parent[index];
        }
        return ans;
    }
};