Најголема подмножество на најголемите деливи парови


Ниво на тешкотија Медиум
Често прашувано во Амазон Google
Динамичко програмирање Математика

Изјава за проблем

Проблемот „Подмножество на најголемите поделливи парови“ наведува дека ви е дадена низа од n различни елементи. Пронајдете ја најголемата должина така што секој пар од подмножеството има поголем елемент делив со помали елементи.

пример

Најголема подмножество на најголемите деливи парови

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

Објаснување

Најголемата подмножество е 1, 2, 4, 8, 16 што ја следи состојбата наведена во проблемот. Бидејќи должината на оваа подгрупа е 5, одговорот е 5.

Пристап

Да почнеме со наивен пристап. Наједноставното нешто на што може да се сети е да се генерираат сите подмножества и потоа да се провери дали подмножеството ја следи дадената состојба. Ако тоа го стори, тогаш зачувајте ја должината на подмножеството. Продолжете да ја ажурирате оваа вредност со поголемата должина на подмножеството, доколку најдете некоја што ја задоволува дадената состојба. Но, овој пристап е многу неефикасен, бидејќи бара создавање на сите подмножества, што за себе бара експоненцијално време.

Значи, со цел ефикасно решавање на проблемот. Проблемот се обидуваме да го разделиме на помали проблеми. Проблемот вели дека сите парови треба да ги исполнуваат условите помалиот број да го дели поголемиот број. Значи, ако размислиме за тоа, можеме да смислиме решение слично на проблемот со ЛИС. Најдолга зголемена последица проблем вели да се најде должината на најголемата подгрупа која е во зголемен редослед. Можеме да направиме нешто слично користејќи Динамичко програмирање. Прво ќе ја сортираме низата. Потоа, за секој елемент, ќе ги видиме сите елементи пред него и ќе провериме дали некој од елементите го дели овој тековен елемент. Ако кој било елемент го дели тековниот елемент, знаеме дека можеме да го додадеме тековниот елемент во тоа подмножество.

Така, ние создаваме низа 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

Анализа на сложеност

Временска комплексност

О (N ^ 2), затоа што во проблемот ги минуваме сите елементи што доаѓаа пред сегашниот елемент. Временската сложеност е полином.

Комплексноста на просторот

НА), бидејќи користевме низа за зачувување на вредностите како табела со ДП. Комплексноста на просторот е линеарна.