ਵੱਡਾ ਵਿਭਾਜਨ ਯੋਗ ਜੋੜਾ ਸਬਸੈੱਟ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਗੂਗਲ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਗਣਿਤ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ “ਸਭ ਤੋਂ ਵੱਡਾ ਵਿਭਾਜਨ ਯੋਗ ਜੋੜਾ ਸਬਸੈੱਟ” ਕਹਿੰਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਵੱਖਰੇ ਵੱਖਰੇ ਤੱਤਾਂ ਦੀ ਲੜੀ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ. ਸਭ ਤੋਂ ਵੱਡੇ ਦੀ ਲੰਬਾਈ ਦਾ ਪਤਾ ਲਗਾਓ ਕਿ ਉਪਗ੍ਰਹਿ ਦੇ ਹਰੇਕ ਜੋੜੇ ਵਿਚ ਛੋਟੇ ਤੱਤ ਦੁਆਰਾ ਵਿਭਾਜਨ ਯੋਗ ਵੱਡਾ ਤੱਤ ਹੁੰਦਾ ਹੈ.

ਉਦਾਹਰਨ

ਵੱਡਾ ਵਿਭਾਜਨ ਯੋਗ ਜੋੜਾ ਸਬਸੈੱਟ

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

ਕਥਾ

ਸਭ ਤੋਂ ਵੱਡਾ ਸਬਸੈੱਟ 1, 2, 4, 8, 16 ਹੈ ਜੋ ਸਮੱਸਿਆ ਵਿੱਚ ਦਰਸਾਈ ਗਈ ਸ਼ਰਤ ਦਾ ਪਾਲਣ ਕਰਦਾ ਹੈ. ਕਿਉਂਕਿ ਇਸ ਉਪਸੈੱਟ ਦੀ ਲੰਬਾਈ 5 ਹੈ, ਉੱਤਰ 5 ਹੈ.

ਪਹੁੰਚ

ਆਓ ਇੱਕ ਭੋਲੇਪਣ ਦੀ ਪਹੁੰਚ ਨਾਲ ਸ਼ੁਰੂਆਤ ਕਰੀਏ. ਸਭ ਤੋਂ ਸੌਖੀ ਗੱਲ ਜਿਸ ਬਾਰੇ ਤੁਸੀਂ ਸੋਚ ਸਕਦੇ ਹੋ ਉਹ ਹੈ ਕਿ ਸਾਰੇ ਸਬਸੈੱਟ ਤਿਆਰ ਕਰਨੇ ਹਨ ਅਤੇ ਫਿਰ ਇਹ ਜਾਂਚਣਾ ਹੈ ਕਿ ਕੀ ਉਪਸੈੱਟ ਦਿੱਤੀ ਗਈ ਸਥਿਤੀ ਨੂੰ ਮੰਨਦਾ ਹੈ. ਜੇ ਇਹ ਕਰਦਾ ਹੈ ਤਾਂ ਸਬਸੈੱਟ ਦੀ ਲੰਬਾਈ ਨੂੰ ਸਟੋਰ ਕਰੋ. ਇਸ ਵੈਲਯੂ ਨੂੰ ਵੱਡੇ ਸਬਸੈੱਟ ਲੰਬਾਈ ਦੇ ਨਾਲ ਅਪਡੇਟ ਕਰਨਾ ਜਾਰੀ ਰੱਖੋ, ਜੇ ਤੁਹਾਨੂੰ ਕੋਈ ਅਜਿਹੀ ਚੀਜ਼ ਮਿਲਦੀ ਹੈ ਜੋ ਦਿੱਤੀ ਗਈ ਸ਼ਰਤ ਨੂੰ ਪੂਰਾ ਕਰਦਾ ਹੈ. ਪਰ ਇਹ ਪਹੁੰਚ ਬਹੁਤ ਅਸਮਰਥ ਹੈ ਕਿਉਂਕਿ ਇਸ ਨੂੰ ਸਾਰੇ ਉਪ-ਸਮੂਹਾਂ ਦੀ ਪੀੜ੍ਹੀ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ ਜਿਸ ਲਈ ਆਪਣੇ ਆਪ ਨੂੰ ਘਾਤਕ ਸਮੇਂ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ.

ਇਸ ਲਈ ਸਮੱਸਿਆ ਨੂੰ ਕੁਸ਼ਲਤਾ ਨਾਲ ਹੱਲ ਕਰਨ ਲਈ. ਅਸੀਂ ਸਮੱਸਿਆ ਨੂੰ ਛੋਟੀਆਂ ਮੁਸ਼ਕਲਾਂ ਵਿੱਚ ਵੰਡਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਦੇ ਹਾਂ. ਸਮੱਸਿਆ ਕਹਿੰਦੀ ਹੈ ਕਿ ਸਾਰੇ ਜੋੜਿਆਂ ਨੂੰ ਇਸ ਸ਼ਰਤ ਨੂੰ ਪੂਰਾ ਕਰਨਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਛੋਟੀ ਸੰਖਿਆ ਨੂੰ ਵੱਡੀ ਸੰਖਿਆ ਵਿੱਚ ਵੰਡਣਾ ਚਾਹੀਦਾ ਹੈ. ਇਸ ਲਈ, ਜੇ ਅਸੀਂ ਇਸ ਬਾਰੇ ਸੋਚਦੇ ਹਾਂ ਤਾਂ ਅਸੀਂ ਐਲਆਈਐਸ ਸਮੱਸਿਆ ਦੇ ਸਮਾਨ ਹੱਲ ਬਾਰੇ ਸੋਚ ਸਕਦੇ ਹਾਂ. ਲੰਮਾ ਵਧਦਾ ਉਪਸਕ੍ਰਿਤੀ ਸਮੱਸਿਆ ਕਹਿੰਦੀ ਹੈ ਕਿ ਸਭ ਤੋਂ ਵੱਡੇ ਸਬਸੈੱਟ ਦੀ ਲੰਬਾਈ ਲੱਭੋ ਜੋ ਕਿ ਵੱਧ ਰਹੇ ਕ੍ਰਮ ਵਿੱਚ ਹੈ. ਅਸੀਂ ਇਸਦੀ ਵਰਤੋਂ ਕਰਕੇ ਕੁਝ ਅਜਿਹਾ ਕਰ ਸਕਦੇ ਹਾਂ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ. ਅਸੀਂ ਪਹਿਲਾਂ ਐਰੇ ਨੂੰ ਸੌਰਟ ਕਰਾਂਗੇ. ਫਿਰ ਹਰੇਕ ਤੱਤ ਲਈ, ਅਸੀਂ ਇਸ ਤੋਂ ਪਹਿਲਾਂ ਸਾਰੇ ਤੱਤ ਵੇਖਾਂਗੇ ਅਤੇ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੋਈ ਤੱਤ ਇਸ ਮੌਜੂਦਾ ਤੱਤ ਨੂੰ ਵੰਡਦਾ ਹੈ. ਜੇ ਕੋਈ ਤੱਤ ਮੌਜੂਦਾ ਤੱਤ ਨੂੰ ਵੰਡਦਾ ਹੈ, ਤਾਂ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਅਸੀਂ ਮੌਜੂਦਾ ਤੱਤ ਨੂੰ ਉਸ ਉਪਸੈੱਟ ਵਿੱਚ ਜੋੜ ਸਕਦੇ ਹਾਂ.

ਇਸ ਤਰ੍ਹਾਂ ਅਸੀਂ ਇੱਕ ਡੀਪੀ ਐਰੇ ਬਣਾਉਂਦੇ ਹਾਂ ਜਿਸਦਾ ਆਈਥ ਐਲੀਮੈਂਟ ਸਭ ਤੋਂ ਵੱਡੇ ਸਬਸੈੱਟ ਦੀ ਲੰਬਾਈ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਮੌਜੂਦਾ ਤੱਤ ਇਸਦਾ ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ ਹੈ. ਅਤੇ ਸਬਸੈੱਟ ਸਮੱਸਿਆ ਤੇ ਲਗਾਈ ਗਈ ਸ਼ਰਤ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਦਾ ਹੈ.

ਕੋਡ

ਸਭ ਤੋਂ ਵੱਡੇ ਵਿਭਾਜਨ ਯੋਗ ਜੋੜਿਆਂ ਲਈ ਸੀ ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ ^ 2), ਕਿਉਂਕਿ ਸਮੱਸਿਆ ਵਿੱਚ ਅਸੀਂ ਉਨ੍ਹਾਂ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਪਾਰ ਕਰਦੇ ਹਾਂ ਜੋ ਮੌਜੂਦਾ ਤੱਤ ਤੋਂ ਪਹਿਲਾਂ ਆਏ ਸਨ. ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਬਹੁਪੱਖੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਡੀ ਪੀ ਟੇਬਲ ਦੇ ਤੌਰ ਤੇ ਵੈਲਯੂਜ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ. ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਲੀਨੀਅਰ ਹੈ.