Walmart⭐ || Easy Solution✔️ || Challenge🏆
"Your thoughts are welcome! \uD83D\uDCAD"\n\n#ReviseWithArsh #6Companies30Days challenge 2k24*\nCompany 2 :- Microsoft\n\nDay1\nQ5. Largest Divisible Subset.\n\
> ***"Your thoughts are welcome! \uD83D\uDCAD"***\n\n***```#ReviseWithArsh #6Companies30Days challenge 2k24```**\n**`` Company 2 :- Microsoft ``***\n\nDay1\nQ5. Largest Divisible Subset.*\n\n![5.largest-divisible-subset.jpg](https://assets.leetcode.com/users/images/77e9f81c-68dc-4106-8649-927c226d4536_1672854594.2094185.jpeg)\n\n### Code\n```java []\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int n = nums.length;\n        if(n==0)return new ArrayList(); //check there is no  value in array\n\n        //Sort an array\n        Arrays.sort(nums); //nlogn\n\n        //Generating count dp\n        int[] count = new int[n];\n        Arrays.fill(count, 1);\n\n        for(int i=1;i<n;i++){ //n^2\n            for(int j=i-1;j>=0;j--){\n                if(nums[i]%nums[j]==0){\n                    count[i]=Math.max(count[i], count[j]+1); // update count of i\n                }\n            }\n        }\n\n        //m axIndex\n        int maxIndex = 0;\n        for(int i=1;i<n;i++){\n            maxIndex=count[i]>count[maxIndex] ? i : maxIndex;\n        }\n\n        //Construct the longest subset\n        List<Integer> result = new ArrayList();\n        int temp = nums[maxIndex];\n        int currentCount = count[maxIndex];\n        for(int i=maxIndex;i>=0;i--){\n            if(temp%nums[i]==0 && currentCount==count[i]){\n                result.add(nums[i]);\n                temp = nums[i];\n                currentCount--;\n            }\n        }\n        return result;\n    }\n}\n```\n*Let\'s collaborate! Join me on GitHub to work on this challenge together* :- \n*[https://github.com/nandini-gangrade/6Companies30Days](GITHUB)*\n\n> ***Happy Coding \uD83D\uDCBB***
['Math', 'Dynamic Programming', 'Java']