تمام وڏا ننibleا حصا ٻٽي سيٽ


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon گوگل
متحرڪ پروگرامنگ Math

مسئلي جو بيان

مسئلو ”سڀني کان وڏي تقسيم ڪندڙ جوڙو” بيان ڪري ٿو ته توهان کي ن مختلف عنصرن جي قطار ڏني وئي آهي. اهڙي وڏي ڊيگهه جي ڊيگهه ڳوليو جو هر نن pairڙي حصي جو نن elementڙو عنصر نن smallerڙن عنصرن طرفان ورهايل هوندو.

مثال

تمام وڏا ننibleا حصا ٻٽي سيٽ

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

وضاحت

سڀ کان وڏو ذيلي حصو 1 ، 2 ، 4 ، 8 ، 16 آهي جيڪو مسئلو ۾ متعين ٿيل شرط جي پيروي ڪري ٿو. ان سب سيٽ جي ڊيگهه 5 آهي ، جواب 5 آهي.

چرچو

اچو ته بي انداز طريقي سان شروع ڪريون. سڀ کان آسان شيءِ جيڪا سڀني لاءِ سمجھي سگھي ٿي ، اھو آھي ته سڀ سبسڪيٽ ٺاھيو ۽ پوءِ چڪاس ڪريو ته ڇا آھي سب سيٽ ڏنل شرط جي مطابق. جيڪڏهن اهو ڪندو ، پوء سبسيٽنگ جي ڊيگهه کي ذخيرو ڪري ٿو. وڏي قيمت جي وڏي ڊيگهه سان هن قيمت کي تازه ڪاري جاري رکون ، جيڪڏهن توهان لڌو ته جيڪو ڏنل شرط کي پورو ڪيو. پر اهو اچڻ انتهائي غير موثر آهي جئين اهو سڀني سبڪن جي نسل جي ضرورت آهي جيڪا پاڻ کي تڪڙو وقت گهرجن.

تنهن ڪري مسئلي کي موثر طور حل ڪرڻ لاءِ. اسان مسئلي کي نن smallerن نن toن مسئلن ۾ ٽوڙڻ جي ڪوشش ڪندا آهيون. مسئلو چوي ٿو سڀني ڀائيوارن کي اها شرط تي مطمئن ڪرڻ گهرجي ته نن numberڙو نمبر وڏي تعداد کي ورهايو وڃي. تنهن ڪري ، جيڪڏهن اسان انهي بابت سوچيو ته اسان ايل آئي ايس مسئلي وانگر ساڳئي حل بابت سوچيو ٿا. تمام گهڻي وڌندڙ پيدوار مسئلو چوي ٿو سڀ کان وڏي ذيلي شيٽ جي ڊيگهه ڳولڻ لاءِ جيڪا ترتيب جي وڌي آهي. اسان ساڳي طريقي سان استعمال ڪري سگهون ٿا متحرڪ پروگرامنگ. اسين پهرين قطار ترتيب ڏينداسين. پوءِ هر عنصر لاءِ ، ڏسندا ان کان اڳ سڀ عنصر ۽ چيڪ ڪندا ته جيڪڏهن ڪنهن به عنصر هن موجوده عنصر کي ورهائي ڇڏيو. جيڪڏهن ڪو عنصر موجوده عنصر کي ورهائي ٿو ، اسان knowاڻون ٿا ته اسين موجوده عنصر کي انهي سب سيٽ ۾ شامل ڪري سگهون ٿا.

اهڙي طرح اسان هڪ ڊي پي صف ٺاهي ٿا جنهن جو عنصر گهڻي ڀا subي جي طول و عرض کي ظاهر ڪري ٿو جنهن کي هاڻوڪو عنصر هن جو سڀ کان وڏو عنصر سمجهيو ويو آهي. ۽ ذيلي مجموعو مسئلو تي لاڳو ڪيل شرط کي پورو ڪري ٿو.

ڪوڊ

وڏن ڊويزبل جوائنٽ سبسيٽنگ لاءِ سي ++ ڪوڊ

#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) ، ڇاڪاڻ ته مسئلي ۾ اسان هاڻوڪي عنصر کان اڳ ٿيندڙ سڀني عنصرن کي لهي چڪا آهيون. وقت جي پيچيدگي پوليٽيڪل آهي.

خلائي پيچيدگي

اي (اين) ، جڏهن کان اسان قدر کي ڊي پي ٽيبل جي طور تي محفوظ ڪرڻ لاءِ استعمال ڪيو آهي. خلائي پيچيدگي لڪير آھي.