सब भन्दा ठूलो विभाजित जोडीहरू सबसेट


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन गुगल
डायनामिक प्रोग्रामिंग गणित

समस्या वक्तव्य

समस्या "सबैभन्दा ठूलो विभाजनशील जोडीहरू उपसेट" भन्छन् कि तपाईंलाई एन फरक तत्वहरूको एर्रे दिइन्छ। सब भन्दा ठूलो को लम्बाई पत्ता लगाउनुहोस् कि सवसेट को प्रत्येक जोडी साना तत्वहरु द्वारा विभाजन योग्य ठूलो तत्व छ।

उदाहरणका

सब भन्दा ठूलो विभाजित जोडीहरू सबसेट

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

स्पष्टीकरण

सबैभन्दा ठूलो सबसेट १, २,,,,, १ is हो जुन समस्यामा निर्दिष्ट शर्त पछ्याउँदछ। यो उपसेटको लम्बाई is हो, उत्तर is हो।

दृष्टिकोण

एक भोली दृष्टिकोण संग सुरू गरौं। सोच्न सजिलो चीज के छ सबै उपसटहरू उत्पन्न गर्न र त्यसपछि जाँच गर्नुहोस् कि उपसेटले दिइएको शर्त पछ्याउँछ। यदि यो गर्छ भने उपसेट को लम्बाई स्टोर। यो मानलाई ठूला सबसेट लम्बाइको साथ अपडेट गर्न जारी राख्नुहोस्, यदि तपाईंले कुनै पनि फेला पार्नुभयो जुन दिइएको शर्तलाई सन्तोष गर्दछ। तर यो दृष्टिकोण अत्यधिक असक्षम छ किनकि यसमा सबै उप-उत्पादनहरू आवश्यक छन् जुन आफैमा घातीय समय चाहिन्छ।

त्यसोभए समस्याको कुशलतापूर्वक समाधान गर्नका लागि। हामी समस्यालाई साना समस्यामा पार्ने प्रयास गर्दछौं। समस्या भन्छ सबै जोडीहरूले यो सन्तुष्टि पूरा गर्नुपर्दछ कि सानो संख्याले ठूलो संख्या विभाजित गर्नुपर्दछ। त्यसोभए, यदि हामी यसको बारेमा सोच्दछौं भने हामी LIS समस्या जस्तै समान समाधानको बारेमा सोच्न सक्छौं। सब भन्दा लामो समय बृद्धि गर्दै समस्याले भन्छ सब भन्दा ठूलो सबसेट को लम्बाई पत्ता लगाउन को लागी जो क्रम बढ्दै छ। हामी पनि यस्तै प्रयोग गरेर गर्न सक्छौं डायनामिक प्रोग्रामिंग। हामी पहिले एरे क्रमबद्ध गर्नेछौं। त्यसो भए प्रत्येक एलिमेन्टको लागि हामी यसको अघि सबै एलिमेन्टहरू देख्नेछौं र यदि कुनै एलिमेन्टले यस हालको एलिमेन्ट्सलाई विभाजन गर्छ भने जाँच गर्दछौं। यदि कुनै तत्वले वर्तमान तत्त्वलाई विभाजित गर्दछ, हामी जान्दछौं कि हामी हालको एलिमेन्ट त्यो सबसेटमा थप्न सक्छौं।

यसैले हामी एक DP एरे सिर्जना गर्दछौं जसको ith एलिमेन्टले सब भन्दा ठूलो सबसेटको लम्बाइलाई जनाउँछ जुनसँग वर्तमान एलिमेन्टसँग यसको सबैभन्दा ठूलो एलिमेन्ट छ। र सबसेट समस्या मा लागी शर्त पूरा गर्दछ।

कोड

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), किनभने समस्यामा हामी सबै तत्वहरू पार गर्दछौं जुन वर्तमान तत्वको अघि आयो। समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (N), किनकि हामीले DP टेबलको रूपमा मानहरू भण्डारण गर्न एर्रे प्रयोग गरेका छौं। ठाउँ जटिलता रैखिक छ।