SHARE
TWEET

largest subset

Farid_Mia59 Nov 16th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // CPP program to find the largest subset which
  2. // where each pair is divisible.
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // function to find the longest Subsequence
  7. int largestSubset(int a[], int n)
  8. {
  9.     // Sort array in increasing order
  10.     sort(a, a + n);
  11.  
  12.     // dp[i] is going to store size of largest
  13.     // divisible subset beginning with a[i].
  14.     int dp[n];
  15.  
  16.     // Since last element is largest, d[n-1] is 1
  17.     dp[n - 1] = 1;
  18.  
  19.     // Fill values for smaller elements.
  20.     for (int i = n - 2; i >= 0; i--) {
  21.  
  22.         // Find all multiples of a[i] and consider
  23.         // the multiple that has largest subset
  24.         // beginning with it.
  25.         int mxm = 0;
  26.         for (int j = i + 1; j < n; j++)
  27.             if (a[j] % a[i] == 0)
  28.                 mxm = max(mxm, dp[j]);
  29.  
  30.         dp[i] = 1 + mxm;
  31.     }
  32.  
  33.     // Return maximum value from dp[]
  34.     return *max_element(dp, dp + n);
  35. }
  36.  
  37. // driver code to check the above function
  38. int main()
  39. {
  40.     int a[] = { 1, 3, 6, 13, 17, 18 };
  41.     int n = sizeof(a) / sizeof(a[0]);
  42.     cout << largestSubset(a, n) << endl;
  43.     return 0;
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top