[Java] Very Understandable Sol || O(n^2) || DP similar to LIS Problem || Inline Comments
\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] v) {\n        \n        //first of all we will sort the input array so that we will ha
```\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] v) {\n        \n        //first of all we will sort the input array so that we will have to check only one conition i.e v[i]%v[j] such that i>j.\n        Arrays.sort(v);\n        int n=v.length;\n        int [] dp=new int[n];\n        \n        //we will initialize the dp array with 1, because there is always a possible set with a single element.\n        Arrays.fill(dp,1);\n        \n        //this step is pretty simple, it is almost exactly as same as Longest Increasing Sequence.\n        for(int i=0;i<n;i++)\n        {\n            \n            // for every v[i] we will check every v[j] before it and if it satisfies our condition i.e v[i]%v[j], we will update our dp[i].\n            for(int j=0;j<i;j++)\n            {\n                if(v[i]%v[j]==0)\n                {\n                    dp[i]=Math.max(dp[i],1+dp[j]);\n                }\n            }\n        }\n        \n        //this step is just for finding the end position(max(dp[i])) of the required set and the size of that set.\n        int ind=0;\n        int m=0;\n        \n        for(int i=0;i<n;i++)\n        {\n            if(m<dp[i])\n            {\n                m=dp[i];\n                ind=i;\n            }\n        }\n        \n        \n        //Now we need m elements in our ans list, obviously the element  v[ind] will be our first element.\n        \n        List<Integer> ans=new ArrayList();\n        ans.add(v[ind]);\n        \n        int last=v[ind];\n        int left=m-1;\n        ind--;\n        //last is actually the last inserted element in the ans list.Because we have sorted the array in ascending order, the next coming           element should divide last inserted one.(we are iterating the array in reverse order) and dp[i] at that position should be equal to         left\n        \n        \n        // Now we need m-1 more elements so we iterate the array from ind-1 and whenever we find and index with dp[i]=left and the last inserted element , last is divisible by v[i] we will insert v[i] into ans list and update last element and elements left to be inserted.\n        for(int i=ind;i>=0;i--)\n        {\n            if(left==0)break;\n            if(dp[i]==left&&last%v[i]==0)\n            {\n                ans.add(v[i]);\n                last=v[i];\n                left--;\n            }\n        }\n        return ans;\n    }\n}\n```\nOverall time complexity of the Solution is O(n^2).\n\nPlease **Upvote** if you liked it.
[]