[C++] | Standard LIS Variation! | Picture + Detailed Explanation + Comments | #NovemberChallenge
This might look like difficult problem but it actually is just a variation of the classic Dynamic Programming problem, Longest Increasing Subsequence. It\'s all
This might look like difficult problem but it actually is just a variation of the classic Dynamic Programming problem, Longest Increasing Subsequence. It\'s all about perspective!\n\n**Intuition & Idea**\n* *Transitivity:* If *z* is divisible by *y*, and *y* is divisible by *x*, then *z* will also be divisible by *x*. In other words, if `z % y == 0` and `y % z == 0`, then `z % x == 0`. Taking some examples will help understand why this works. For instance, take `x = 3, y = 6, z = 18`. \n* *Sorting:* If we only focus on achieving transitivity for every three numbers in our subset, then also we will get the answer. And since the numbers are distinct, then `x < y < z`. Hence sorting the numbers before processing and then trying to achieve transitivity makes sense!\n* *LIS:* Once we have sorted our array, then this problem becomes very similar to LIS. It\'s just that instead of finding the Longest *Increasing* Subsequence, we want to look for the Longest *Divisible* Subsequence/Subset. Hence the algorithm will slightly vary, but the core idea will remain the same. So here, *dp[i]* will represent the length of the longest divisible subsequence which ends at the ith index. The state change would look something like this:\n```\nfor j in [0, i - 1]:\n\tif nums[j] divides nums[i]:\n\t\tif dp[i] + 1 > dp[j]:\n\t\t\tdp[j] = dp[i] + 1\n``` \n* *Obtaining Subset:* Now that we have the length of the Longest Divisible Subset and know the index where it ends, how do be obtain the entire set? From the above mentioned pseudo code, it is clear that for every *dp[i]*, there will be one *dp[j]* which will preceed it. So we basically need to store this *jth* index which represents the predecessor of the *ith* index. For this, we can simply use another array which tracks predecessors of every index! \n\n**Example**\nRefer to the following picture for better understanding!\n![image](https://assets.leetcode.com/users/images/780c6367-489a-4466-a222-621416eabfa1_1636937464.6503174.png)\nThe cells in red in the final row (1, 2, 4, 8) depict the Largest Divisible Subset!\n\n**Implementation**\nThe code is very similar to the traditional LIS. I have used an extra array *child* to track predecessors of indices. Hence, *dp[i]* will tell the length of the Longest Divisible Subset ending at the *ith* index, and *child[i]* will tell the index which comes before the *ith* index in the subset which includes the *ith* index. *child[i]* will be -1, if the *ith* index is the first element in the subset.\n\n**C++**\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        \n        // Sorting: to leverage the transitive property!\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        \n        // Initializing the DP and CHILD arrays\n        vector<int> dp(n, 1), child(n, -1);\n        \n        int imax = 0;\n        \n        for(int i = 1; i < n; i++) {\n            \n            // Considering ith element as the last element\n            // and finding the largest subset it can \n            // belong to\n            for(int j = 0; j < i; j++) {\n                \n                // Using transitivity, if nums[i] % nums[j] == 0\n                // then all numbers in the subset ending at j\n                // will divide num[i] as well!\n                if(nums[i] % nums[j] == 0) {\n                    \n                    // Inclusion of i will increase the size of \n                    // the subset by 1\n                    if(1 + dp[j] > dp[i]) {\n                        dp[i] = 1 + dp[j];\n                        \n                        // Setting the predecessor of i\n                        child[i] = j;\n                    }\n                }\n            }\n            \n            // Determining the index where the largest subset ends\n            if(dp[i] > dp[imax]) {\n                imax = i;\n            }\n        }\n        \n        vector<int> ans;\n        \n        // Backtracking to obtain the entire largest subset!\n        // This condition makes sure that the loop stops\n        // once the first element of the subset is traversed\n        while(imax != -1) {\n            ans.push_back(nums[imax]);\n            imax = child[imax];\n        }\n        \n        return ans;\n    }\n};\n```\n\n**Complexity Analysis**\n*Space Complexity: O(n)*\n*Time Complexity: O(n^2)*
[]