Longest Increasing Subsequence variant | With explaination
Intuition\nThe problem asks us to find the largest subset of distinct positive integers where each pair of elements satisfies a specific condition. To solve thi
# Intuition\nThe problem asks us to find the largest subset of distinct positive integers where each pair of elements satisfies a specific condition. To solve this problem efficiently, we can use dynamic programming.\n\n# Approach\n1. Sort the given input array nums in ascending order. Sorting the array ensures that if nums[i] is divisible by nums[j], then nums[j] will always appear before nums[i] in the sorted array.\n2. Create a 2D vector dp of size nums.size(). Each element of dp will be a vector that stores the largest subset of elements ending at index i.\n3. Iterate through each element in nums using the outer loop. For each element at index i, iterate through all the previous elements using the inner loop (from 0 to i-1).\n4. Check if nums[i] is divisible by nums[j] using the condition nums[i] % nums[j] == 0.\n    - If the condition is satisfied, update dp[i] with the larger subset among dp[i] and dp[j], where dp[j] represents the largest subset ending at index j.\n5. After the inner loop, add the current element nums[i] to dp[i] to include it in the subset.\n6. Compare the size of the current subset dp[i] with the size of the current largest subset ans. If dp[i] is larger, update ans with dp[i].\n7. After the outer loop, ans will contain the largest subset of distinct positive integers satisfying the given conditions. Return ans.\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is O(n^2), where n is the size of the input array nums. The outer loop runs for n iterations, and the inner loop also runs for a maximum of n iterations.\n\n- Space complexity:\nThe space complexity is O(n^2) as well. The dp vector has a size of n, and each element of dp is a vector that can have a maximum size of n in the worst case (when all elements of nums form a valid subset).\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        vector<int> ans;\n        vector<vector<int>> dp(nums.size());\n        \n        for(int i = 0;i<nums.size();i++){\n            for(int j = 0;j<i;j++){\n                if(nums[i]%nums[j] == 0 && dp[j].size()>dp[i].size()){\n                    dp[i] = dp[j];\n                }\n            }\n            dp[i].push_back(nums[i]);\n            if(ans.size()<dp[i].size())ans = dp[i];\n        }\n\n        return ans;\n    }\n};\n```
['C++']