Beat 100% Users || Simple || C++/Java/Python || With Explanation
Please upvote if you find the solution helpful.  \n\n\n## Explanation\n\n- Initialization:\n\n  - Initialize vectors dp and prev_index, and a variable maxi.\n  
Please **upvote** if you find the solution helpful.  \n![image](https://assets.leetcode.com/users/images/4cb60b8b-9265-4b3b-966a-d4cbfecc90b8_1707437929.5995922.png)\n\n## Explanation\n\n- **Initialization:**\n\n  - Initialize vectors `dp` and `prev_index`, and a variable `maxi`.\n  - Sort the input vector in ascending order.\n\n- **Dynamic Programming:**\n  - Iterate over pairs of indices `(i, j)` to find divisible elements.\n  - Update `dp` and `prev_index` if a larger subset is found.\n  - Update `maxi` to track the index of the maximum subset.\n\n- **Subset Reconstruction:**\n  - Initialize an empty vector `result`.\n  - Reconstruct the largest divisible subset using `prev_index`.\n  - Start from `maxi` and backtrack through `prev_index` to obtain the subset elements.\n\n- **Finalization:**\n  - Reverse the `result` vector to maintain the correct order.\n  - Return the resulting vector representing the largest divisible subset.\n\n**Time Complexity: O(n ^2)**\n**Space Complexity: O(n)**\n**C++**\n```\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        //Handle empty input\n        if (nums.size() == 0) return {};\n\n        // Sort the array\n        sort(nums.begin(), nums.end());\n\n        // Initialize arrays for dynamic programming\n        vector<int> dp(nums.size(), 1);  // Lengths of largest divisible subsets ending at each index\n        vector<int> prev_index(nums.size(), -1);  // Indices of previous numbers in the subsets\n\n        // Find the largest divisible subset lengths\n        int maxi = 0;  // Index of the longest subset found so far\n        for (int i = 1; i < nums.size(); i++) {\n            for (int j = 0; j < i; j++) {\n                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {\n                    dp[i] = dp[j] + 1;\n                    prev_index[i] = j;\n                    if (dp[i] > dp[maxi]) {\n                        maxi = i;  // Update index of the longest subset\n                    }\n                }\n            }\n        }\n\n        // Reconstruct the largest divisible subset\n        vector<int> result;\n        while (maxi >= 0) {\n            result.push_back(nums[maxi]);\n            maxi = prev_index[maxi];\n        }\n\n        // Reverse the result to get ascending order\n        reverse(result.begin(), result.end());\n        return result;\n    }\n};\n```\n**python**\n```\nclass Solution:\n    def largestDivisibleSubset(self, nums):\n        n = len(nums)\n        if n == 0:\n            return []\n        \n        nums.sort()\n        dp = [1] * n\n        prev_index = [-1] * n\n        maxi = 0\n        \n        for i in range(1, n):\n            for j in range(i):\n                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:\n                    dp[i] = dp[j] + 1\n                    prev_index[i] = j\n                    if dp[i] > dp[maxi]:\n                        maxi = i\n        \n        result = []\n        while maxi >= 0:\n            result.append(nums[maxi])\n            maxi = prev_index[maxi]\n        \n        result.reverse()\n        return result\n```\n```\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int n = nums.length;\n        if (n == 0) return new ArrayList<>();\n        \n        Arrays.sort(nums);\n        int[] dp = new int[n];\n        int[] prev_index = new int[n];\n        Arrays.fill(dp, 1);\n        Arrays.fill(prev_index, -1);\n        int maxi = 0;\n        \n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {\n                    dp[i] = dp[j] + 1;\n                    prev_index[i] = j;\n                    if (dp[i] > dp[maxi])\n                        maxi = i;\n                }\n            }\n        }\n        \n        List<Integer> result = new ArrayList<>();\n        while (maxi >= 0) {\n            result.add(nums[maxi]);\n            maxi = prev_index[maxi];\n        }\n        \n        Collections.reverse(result);\n        return result;\n    }\n}\n```\n![image](https://assets.leetcode.com/users/images/356929c7-5780-45f4-8eb5-3299da5725d8_1707009629.3697278.jpeg)
['C', 'Python', 'Java']