అతిపెద్ద విభజించదగిన జతలు ఉపసమితి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్
డైనమిక్ ప్రోగ్రామింగ్ మఠం

సమస్యల నివేదిక

“అతిపెద్ద విభజించదగిన జతల ఉపసమితి” సమస్య మీకు n విభిన్న మూలకాల శ్రేణిని ఇస్తుందని పేర్కొంది. ఉపసమితి యొక్క ప్రతి జత చిన్న మూలకాలతో విభజించబడే పెద్ద మూలకాన్ని కలిగి ఉన్న అతిపెద్ద పొడవును కనుగొనండి.

ఉదాహరణ

అతిపెద్ద విభజించదగిన జతలు ఉపసమితి

array = {1, 2, 4, 5, 8, 9, 16}
5

వివరణ

అతిపెద్ద ఉపసమితి 1, 2, 4, 8, 16, ఇది సమస్యలో పేర్కొన్న పరిస్థితిని అనుసరిస్తుంది. ఈ ఉపసమితి యొక్క పొడవు 5 కాబట్టి, సమాధానం 5.

అప్రోచ్

అమాయక విధానంతో ప్రారంభిద్దాం. ఒకరు ఆలోచించగలిగే సరళమైన విషయం ఏమిటంటే, అన్ని ఉపసమితులను ఉత్పత్తి చేసి, ఆపై ఇచ్చిన ఉపసమితిని ఉపసమితి అనుసరిస్తుందో లేదో తనిఖీ చేయండి. అది చేస్తే ఉపసమితి యొక్క పొడవును నిల్వ చేయండి. మీరు ఇచ్చిన పరిస్థితిని సంతృప్తిపరిచే ఏదైనా కనుగొంటే, ఈ విలువను పెద్ద ఉపసమితి పొడవుతో నవీకరించడం కొనసాగించండి. కానీ ఈ విధానం చాలా అసమర్థంగా ఉంటుంది, ఎందుకంటే దీనికి అన్ని ఉపసమితుల తరం అవసరం, దీనికి ఘాతాంక సమయం అవసరం.

కాబట్టి సమస్యను సమర్థవంతంగా పరిష్కరించడానికి. మేము సమస్యను చిన్న సమస్యలుగా విభజించడానికి ప్రయత్నిస్తాము. అన్ని జతలు చిన్న సంఖ్య పెద్ద సంఖ్యను విభజించాలనే పరిస్థితిని సంతృప్తి పరచాలని సమస్య చెబుతుంది. కాబట్టి, మేము దాని గురించి ఆలోచిస్తే, LIS సమస్యకు సమానమైన పరిష్కారం గురించి ఆలోచించవచ్చు. పొడవైన పెరుగుతున్న పరిణామం పెరుగుతున్న క్రమంలో ఉన్న అతిపెద్ద ఉపసమితి యొక్క పొడవును కనుగొనమని సమస్య చెబుతుంది. ఇలాంటిదే మనం ఉపయోగించుకోవచ్చు డైనమిక్ ప్రోగ్రామింగ్. మేము మొదట శ్రేణిని క్రమబద్ధీకరిస్తాము. అప్పుడు ప్రతి మూలకం కోసం, దాని ముందు ఉన్న అన్ని మూలకాలను చూస్తాము మరియు మూలకాలు ఏవైనా ఈ ప్రస్తుత మూలకాన్ని విభజిస్తాయో లేదో తనిఖీ చేస్తాము. ఏదైనా మూలకం ప్రస్తుత మూలకాన్ని విభజిస్తే, ప్రస్తుత మూలకాన్ని ఆ ఉపసమితికి జోడించగలమని మనకు తెలుసు.

ఈ విధంగా మేము ఒక DP శ్రేణిని సృష్టిస్తాము, దీని మూలకం ప్రస్తుత మూలకాన్ని దాని అతిపెద్ద మూలకంగా కలిగి ఉన్న అతిపెద్ద ఉపసమితి యొక్క పొడవును సూచిస్తుంది. మరియు ఉపసమితి సమస్యపై విధించిన పరిస్థితిని సంతృప్తిపరుస్తుంది.

కోడ్

అతిపెద్ద విభజించదగిన జతల ఉపసమితి కోసం C ++ కోడ్

#include<bits/stdc++.h>
using namespace std;

int largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n==0)return 0;
    sort(nums.begin(), nums.end());
    int dp[n], ans = INT_MIN;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=i-1;j>=0;j--)
            if(nums[i]%nums[j] == 0){
                if((dp[j]+1)>dp[i]){
                    dp[i] = dp[j]+1;
                    ans = max(ans, dp[i]);
                }
            }
    }
    return ans;
}

int main(){
  int n;cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  int len = largestDivisibleSubset(v);
  cout<<len<<endl;
}
7
1 2 4 5 8 9 16
5

అతిపెద్ద విభజించదగిన జతల ఉపసమితి కోసం జావా కోడ్

import java.util.*;
class Main{
  
  static int largestDivisibleSubset(ArrayList<Integer> nums) {
      int n = nums.size();
      if(n==0)return 0;
      Collections.sort(nums);
      int dp[] = new int[n];
      int ans = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          dp[i] = 1;
          for(int j=i-1;j>=0;j--)
              if(nums.get(i)%nums.get(j) == 0){
                  if((dp[j]+1)>dp[i]){
                      dp[i] = dp[j]+1;
                      ans = Math.max(ans, dp[i]);
                  }
              }
      }
      return ans;
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> v = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      v.add(a);
    }
    int len = largestDivisibleSubset(v);
    System.out.println(len);
  	}
}
7
1 2 4 5 8 9 16
5

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N ^ 2), ఎందుకంటే సమస్యలో ప్రస్తుత మూలకానికి ముందు వచ్చిన అన్ని అంశాలపై మేము ప్రయాణిస్తాము. సమయం సంక్లిష్టత బహుపది.

అంతరిక్ష సంక్లిష్టత

పై), విలువలను DP పట్టికగా నిల్వ చేయడానికి మేము శ్రేణిని ఉపయోగించాము కాబట్టి. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.