3 STEPS [c++ | python | java] [dp] PEN PAPER DIAGRAM
NOTE:- if you found anyone\'s post helpful please upvote that post because some persons are downvoting unneccesarily, and you are the one guys that save our pos
***NOTE:- if you found anyone\'s post helpful please upvote that post because some persons are downvoting unneccesarily, and you are the one guys that save our post from getting unvisible, upvote for remains visible for others so and other people can also get benefitted***\n\n**DESCRIPTION:-**\n\n**Given an array the task is to largest divisible subset in array. A subset is called divisible if for every pair (x, y) in subset, either x divides y or y divides x.**\n\n**Examples:**\n\nInput  : arr[] = {1, 16, 7, 8, 4}\nOutput : 16 8 4 1 or 1 4 8 16\n\n**An efficient solution involves following steps.**\n\n**1.  Sort all array elements in increasing order. The purpose of sorting is to make sure that all divisors of an element appear before it.\n2.  Create an array dp[] of same size as input array. dp[i] stores size of divisible subset ending with arr[i] (In sorted array). The minimum value of dp[i] would be 1.\n3.  Traverse all array elements. For every element, find a divisor arr[j] with largest value of dp[j] and store the value of dp[i] as dp[j] + 1.**\n\n![image](https://assets.leetcode.com/users/amit_gupta10/image_1592042710.png)\n\n\n\n\n\n\n\n\n\n\n\n\n**c++ code**\n\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        if(nums.size()==0){\n            return nums;\n        }\n        sort(nums.begin(),nums.end());\n        int flag=1;\n        if(nums[0]==1){\n            flag=0;\n        }\n        else{\n            nums.push_back(1);\n            flag=1;\n        }\n        sort(nums.begin(),nums.end());\n        int i,j;\n        int dp[nums.size()][2];\n        for(i=nums.size()-1;i>=0;i--){\n            dp[i][0]=0;\n            dp[i][1]=i;\n            for(j=i+1;j<nums.size();j++){\n                if((nums[j]%nums[i])==0){\n                    if(dp[j][0]>dp[i][0]){\n                        dp[i][0]=dp[j][0];\n                        dp[i][1]=j;\n                    }  \n                }\n            }\n            dp[i][0]++;\n        }\n        i=0;\n        vector<int> t;\n        t.push_back(nums[i]);\n        while(dp[i][1]!=i){\n            i=dp[i][1];\n            t.push_back(nums[i]);\n            \n        }\n        if(flag==1){\n            t.erase(t.begin());\n        }\n        return t;\n        \n    }\n};\n```\n\n*Runtime: 52 ms, faster than 43.10% of C++ online submissions for Largest Divisible Subset.\nMemory Usage: 8.6 MB, less than 52.64% of C++ online submissions for Largest Divisible Subset.*\n\n**python code**\n\n```\nclass Solution(object):\n     def largestDivisibleSubset(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[int]\n        """\n        n = len(nums)\n        if n <= 1:\n            return nums\n        nums.sort()\n        dp = [(0, 0)] * n\n        dp[0] = (1, 0)\n        maxIndex, maxVal = 0, 1\n        for i in range(1, n):\n            dp[i] = max((dp[j][0] + 1, j) for j in range(i + 1) if nums[i] % nums[j] is 0)\n            if dp[i] > maxVal:\n                maxIndex, maxVal = i, dp[i]\n        i, lds = maxIndex, [nums[maxIndex]]\n        while i != dp[i][1]:\n            i = dp[i][1]\n            lds.append(nums[i])\n        return lds\n        \n```\n\n*Runtime: 436 ms, faster than 26.39% of Python online submissions for Largest Divisible Subset.\nMemory Usage: 13 MB, less than 24.36% of Python online submissions for Largest Divisible Subset.*\n\n\n**java**\n\n```\nclass Solution {\n  // if we sort the array, every element in a divisibleSubset can be divisible by the element just before it.\n// for any element k, its largestDivisibleSubset that ends with k can be formed in the following way: \n// use element k after any one of the previous elements that is divisble \npublic List<Integer> largestDivisibleSubset(int[] nums) {\n    int[] l = new int[nums.length]; // the length of largestDivisibleSubset that ends with element i\n    int[] prev = new int[nums.length]; // the previous index of element i in the largestDivisibleSubset ends with element i\n    \n    Arrays.sort(nums);\n    \n    int max = 0;\n    int index = -1;\n    for (int i = 0; i < nums.length; i++){\n        l[i] = 1;\n        prev[i] = -1;\n        for (int j = i - 1; j >= 0; j--){\n            if (nums[i] % nums[j] == 0 && l[j] + 1 > l[i]){\n                l[i] = l[j] + 1;\n                prev[i] = j;\n            }\n        }\n        if (l[i] > max){\n            max = l[i];\n            index = i;\n        }\n    }\n    List<Integer> res = new ArrayList<Integer>();\n    while (index != -1){\n        res.add(nums[index]);\n        index = prev[index];\n    }\n    return res;\n}\n\n}\n```\n\n*Runtime: 16 ms, faster than 78.50% of Java online submissions for Largest Divisible Subset.\nMemory Usage: 39.4 MB, less than 87.96% of Java online submissions for Largest Divisible Subset.*\n\nreferences:-  geeks\n\n**if it helps please upvote if you have any doubt comment it**
[]