✔✔ Easy || Fast || LIS Variation || Simple Explanation
\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) \n    {\n        int n = nums.size();\n        vector<int > dp(n,1);    /
```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) \n    {\n        int n = nums.size();\n        vector<int > dp(n,1);    // create a dp vector for storing the longest subset till the index i which satisfies the divisibility condition  initially dp vector is filled with 1 (since every element itself is a subset with length 1 )\n\t\t\n\t\t\n        int ans = 0;\n        vector<int > store(n,0);      // vector store is used to store the index of the previously included elements\n\t\t\n        int lastId = 0;\n\t\t\n        // 1) sort the given array  so that we need to check only in for A[i] % A[j] not A[j] % A[i] provided  i > j\n\t\t\n        sort(nums.begin(), nums.end());\n\n        for(int i=0; i<n; i++)\n        {\n            store[i] = i;           \n            for(int j=0; j<i; j++)\n            {\n                if(nums[i] % nums[j] == 0 && dp[i] < 1 + dp[j])\n                {\n                    dp[i] = 1 + dp[j];\n                    store[i] = j;\n                }\n            }\n\n            if(ans < dp[i])\n            {\n                ans = dp[i];\n                lastId = i;         // stores the index where we got max length of the subset  \n            }\n        }\n\n\n        vector<int > printAns;      // vector for storing the answer \n\n        printAns.push_back(nums[lastId]);\n\n\n        while(store[lastId] != lastId)\n        {\n            lastId = store[lastId];\n            printAns.push_back(nums[lastId]);\n        }\n\t\t\n\t\t  // since we have our answer in reverse order, so just reversed it -> \n\t\t   \n        reverse(printAns.begin(), printAns.end());    \n\n        return printAns;\n\n    }\n};\n\n// Please upvote if it helps you \uD83D\uDE0A\uD83D\uDE0A\n\n```
['Dynamic Programming', 'C++']