Advertisement
prakharvk

longest subset such that max of every pair in it is divisible by min

Jun 21st, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int calc(vector<int>&v){
  4.     int n=v.size();
  5.     if(n==0)
  6.         return 0;
  7.     vector<int>dp(n);
  8.     dp[n-1]=1;
  9.     int ans=INT_MIN;
  10.     for(int i=n-2;i>=0;i--){
  11.         int temp=0;
  12.  
  13.         for(int j=i+1;j<n;j++){
  14.             if(v[j]%v[i]==0){
  15.                 temp=max(temp,dp[j]);
  16.             }
  17.         }
  18.         dp[i]=temp+1;
  19.         ans=max(ans,dp[i]);
  20.     }
  21.     return ans;
  22. }
  23.  
  24. int main(){
  25.     int n;
  26.     cin>>n;
  27.     vector<int>v(n);
  28.     for(int i=0;i<n;i++){
  29.         cin>>v[i];
  30.     }
  31.     int ans=calc(v);
  32.     cout<<ans;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement