📌✅ Similar to print LIS , Java Code, Intutive and Visualization
This problem is similar to restoring longest subsequence  or print longest subsequence \nref here : https://cp-algorithms.com/sequences/longest_increasing_subse
This problem is similar to restoring longest subsequence  or print longest subsequence \nref here : https://cp-algorithms.com/sequences/longest_increasing_subsequence.html\n\n\n\n**visualize our problem by dp**\n\n#### steps:\n*  **store prevIndex to know index of previous element of subset , help in retrive back subset**\n*  **len is used to know maxlen subset ending at current index** \n\n\n```\n[2,3,4,8,9]  ans:[2,4,8]\n\nidx               0   1    2     3      4    5     6    7\n               ---------------------------------------------\narr              [1 , 2  ,  3  ,  6  ,  36 , 64 , 128 , 256 ]\nlength/dp         1  | 2  |  2  |  3  |  4  |  3 | 4   | 5\n            ----------------------------------------------\nprevIndex         -1 |  0 |  -1  | 1  |  3  |  1 |  5  | 6\n\nans: [256,128,64,2,1]\n```\n\n\n```\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int dp[] =   new int[nums.length];\n        int prev[] =  new int[nums.length];\n        Arrays.sort(nums);\n        int maxlen = 0,end = 0, n =  nums.length;\n        for(int i=0;i<n;i++){\n            int count  =  1;\n            int previdx = -1;\n            for(int j=i-1;j>=0;j--){\n                if(nums[i]%nums[j]==0 && dp[j]+1>count ){\n                    count =  dp[j]+1;\n                    previdx = j;                    \n                }\n            }\n            dp[i] = count;\n            prev[i] = previdx;\n            \n            if(dp[i]>maxlen){\n                maxlen =  dp[i];\n                end =  i;\n            }                        \n        }\n        ArrayList<Integer> ans =  new ArrayList<Integer>();\n        while(end!=-1){\n            ans.add(nums[end]);\n            end =  prev[end];\n        }\n        \n        return ans;\n        \n    }\n}\n```\n\n## comment below if any doubt left \n### Upvote if find helpful\n\n
['Dynamic Programming', 'Java']