• API
• FAQ
• Tools
• Archive
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);
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.

Top