✅ [C++] EASY Solution || Standard LIS Variation || INTUITIVE approach
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
***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 disappearing.***\n\nNow, we have to find the largest divisible subset in a vector of unique integers. In a Divisible subset for all pairs (x, y), we have a propert of either x divides y or y divides x completely, i.e. `x%y==0 or y%x==0`\n\n**Idea of the problem:** This problem is a slight variation of a standard DP problem that is Longest Increasing Subsequence. (P.S. If you don\'t know about LIS, then It would be better to learn LIS first then read this post).\n\n**My Approach:**\n1. We will first sort our vector so that when we are traversing the array, we will always know that the divisor for current element (at index `i` )lies on the left side of the array i.e. `at position less that i`.\n\n2. So, we just need to change this one condition in LIS (Longest Increasing Subsequence) algorithm. We need to find the longest increasing subsequence keeping in mind that the current element is getting divided by the last element of previously longest increasing subsequence (I will give the proof of correctness at the end of the code if some people are eager to know more about it)\n\n3. I will keep the track of previous index for any current index in a LIS as it will help us in generating the sequence itself.\n\nHere goes the code for the approach I mentioned above:\n\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& arr) {\n        \n        int n = arr.size();\n\t\t\n\t\t// Sorting step\n        sort(arr.begin(), arr.end());\n        \n        vector<int> lis(n, 1); // This will keep the length of LIS that obeys our property of divide\n\t\tvector<int>prev_idx(n, -1); // previous index array to track for previous element in the lis before i\n        int max{}, index{};\n \n        for(int i{}; i<n; ++i){\n            \n            for(int j{i-1}; j>=0; --j){\n                \n\t\t\t\t// Here we know arr[i] > arr[j] because of sorting so if arr[j] divides arr[i]\n\t\t\t\t// and adding arr[j] to the LIS of arr[i] increases the size of LIS of arr[i],\n\t\t\t\t// then we will update the LIS of arr[i] and we store j i.e. the prev index for i in our sequence\n                if(lis[j]+1 > lis[i] && arr[i]%arr[j] == 0){\n                    \n                    lis[i] = lis[j] + 1;\n                    prev_idx[i] = j;\n                }\n            }\n        }\n\t\t\n\t\t// Compute the last index in our LIS that will be the maximum length LIS\n\t\tfor(int i{}; i<n; ++i){\n            \n            if(max < lis[i]){\n                max = lis[i];\n                index = i;\n            }\n        }\n        \n        vector<int>divisible_subset{};\n        \n\t\t// Traverse from last index to the first index in our LIS\n\t\t// and add elements to our result\n        while(index != -1){\n            \n            divisible_subset.push_back(arr[index]);\n            index = prev_idx[index];\n        }\n        \n        return divisible_subset;\n    }\n};\n```\n\n**Time Complexity:** ***O(N x log(N)) + O(N^2) ~ O(N^2)***\n**Space Complexity:** ***O(2N) ~ O(N)***\n\n**Proof of correctness:**\n\nLet\'s say till now we have `[b, c]` in our LIS that has been constructed so far and our current element is `x`.\n\nNow if `x%c == 0` (we know `c<=x` because vector is sorted) then it means `c divides x`\n-> `x = c * k1`\n-> since `b divides c`, we have `c = b * k2`\n-> hence `x = c * k1 = (b * k2) * k1 = b * K`\n-> hence `b also divides x`\n\nThis was the intuition behind the sorting and the checking part of our LIS algorithm\n\nHope I made it easy enough for you to understand!\n**Please Upvote \uD83D\uDD3C if this post helped you!**\n
[]