fork download
copy 
  1. /*
  2. The key concept here is:
  3. Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.
  4.  
  5. For example, let's say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.
  6.  
  7. For an increasingly sorted array of integers a[1 .. n]
  8.  
  9. T[n] = the length of the largest divisible subset whose largest number is a[n]
  10.  
  11. T[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }
  12.  
  13.  
  14. */
  15.  
  16. class Solution {
  17. public:
  18.     vector<int> largestDivisibleSubset(vector<int>& v) 
  19.     {
  20.         vector<int> aans;
  21.         if(v.size()==0)
  22.  
  23.         return aans;
  24.  
  25.         if(v.size()==1)
  26.         {
  27.             aans.push_back(v[0]);
  28.             return aans;
  29.         }
  30.         sort(v.begin(),v.end());
  31.         int n=v.size();
  32.         vector<int> p(n,-1);
  33.         int dp[n];
  34.         dp[0]=1;
  35.        // cout<<"heelloo";
  36.         int j;
  37.         int max2=1;
  38.         for(int i=1;i<n;i++)
  39.         {
  40.             dp[i]=1;
  41.             for(int j=0;j<i;j++)
  42.             {
  43.                 if(v[i]%v[j]==0 && dp[i]<1+dp[j])
  44.                 {
  45.                     dp[i]=1+dp[j];
  46.                     p[i]=j;
  47.                 }
  48.             }
  49.  
  50.             //till now maximum dp
  51.  
  52.             if(max2<dp[i])
  53.             {
  54.                 max2=dp[i];
  55.                 j=i;
  56.             }
  57.         }
  58.        // cout<<"heelloo"<<j;
  59.         vector<int> ans;
  60.         for(int k=j;k!=-1;k=p[k])
  61.         ans.push_back(v[k]);
  62.  
  63.         if(ans.size()==0)
  64.         {
  65.             ans.push_back(v[0]);
  66.         }
  67.         //cout<<"heelloo";
  68.         reverse(ans.begin(),ans.end());
  69.  
  70.         return ans;
  71.  
  72.  
  73.  
  74.     }
  75. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:18:5: error: ‘vector’ does not name a type
     vector<int> largestDivisibleSubset(vector<int>& v)
     ^~~~~~
stdout
copy 
Standard output is empty
https://ideone.com/bzmuM0
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!