Simple Intuitive Approach c++| DP | Storing max length for current from any Prev Element
I got a very simple and intutitve approach to solve this problem . The logic that clicked me as soon as I read the problem was that if a[i]%a[j]==0 && a[j]&a[k]
I got a very simple and intutitve approach to solve this problem . The logic that clicked me as soon as I read the problem was that if a[i]%a[j]==0 && a[j]&a[k]==0 , then definetly a[i]%a[k]==0 . So , to find the max length subset i just want an a[i]%a[j]==0 such that a[j] already has max length among all a[i]%a[j]==0.\n\nSo, firstly i sort the array , the iterate through the array . I keep track of score of each index (i.e. max length of subset it can form) . So , if for any i , we find any j<i , such that a[i]%a[j]==0 and score[j] is max among all j that satisfy this condition, we make current score[i]=score[j]+1, as we now add just one element to the subset .\n\nFor ex , we have  4,8,10,2400 . so if we are at 2400 , we find 2400%10==0, but Score->10 calculated earlier is 0, so we take 8 , as it satisfies 2400%8==0 and also has a better than than 10 . Now score->2400 becomes score->8+1.\n\nWe store both the maximum score and the index that has maximum score . Now we just keep adding elements from last element that has max score and decrease our score and check whether current a[i] satisfies (last%a[i]==0 \n&& score[i]==maxcur).\n\nHere , we used dp technique as we use score of previous items to calculate score of current item\n\n```\n    vector<int> largestDivisibleSubset(vector<int>& a) {\n        int n=a.size();\n        sort(a.begin(),a.end());\n        vector<int> score(n,0);\n        int mx=0,mxi=0;\n        for(int i=1;i<n;i++){\n            for(int j=0;j<i;j++){\n                if(a[i]%a[j]==0 && score[j]+1>score[i]){score[i]=score[j]+1;}\n            }\n            if(score[i]>mx){mx=score[i];mxi=i;}\n        }\n        vector<int> ans;\n        ans.push_back(a[mxi]);mx--;\n        int last=a[mxi];\n        for(int i=mxi-1;i>=0;i--){\n            if(last%a[i]==0 && score[i]==mx){\n                ans.push_back(a[i]);mx--;last=a[i];\n            }\n        }\n        if(ans.size()==0){ans.push_back(a[0]);}\n        return ans;\n    }\n\t\n\t\n\tPlease like and comment your approach for this problem!!!\n
['Dynamic Programming', 'C']