طباعة سلسلة الطول الأقصى للأزواج


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون
البرمجة الديناميكية

المشكلة بيان

تنص مشكلة "طباعة سلسلة الطول الأقصى للأزواج" على أنه تم إعطاؤك بعض أزواج الأرقام. من المسلم به أن الرقم الأول في كل زوج أصغر من الرقم الثاني. أنت الآن بحاجة إلى إيجاد أطول سلسلة بحيث يكون الرقم الثاني للزوج السابق (أ ، ب) أصغر من الرقم الأول التالي بعد الزوج (ج ، د) أي (ب <ج).

مثال

(1, 10), (11, 25), (26, 35), (36, 50)
(1, 10), (11, 25), (26, 35), (36, 50)

تفسير

اخترنا جميع الأزواج لأن جميع الأزواج المعينة استوفت الشرط.

(1, 2), (10, 30), (5, 6), (15, 25), (17, 21)
(1, 2), (5, 6), (10, 30)

تفسير

الزوج الثالث الذي اخترناه لا يهم. كان بإمكاننا اختيار أي من الأزواج الثلاثة المتبقية لأنهم جميعًا استوفوا الشرط. لكن لا يمكننا اختيار أي اثنين من الثلاثة المتبقية.

نهج لطباعة سلسلة الطول الأقصى للأزواج

تطلب منا المشكلة إيجاد وطباعة أقصى طول لسلسلة أزواج. إذن ماذا يعني الحد الأقصى للطول هنا؟ يمثل الحد الأقصى للطول هنا عدد الأزواج في النتيجة. إذن ، في النهاية ، علينا إيجاد تلك الأزواج التي تشكل أقصى طول.

لقد ناقشنا بالفعل هذه المشكلة. طلبت منا المشكلة التي ناقشناها إيجاد الطول الأقصى. هناك ناقشنا الأساليب المختلفة لمعالجة المشكلة. هنا في هذا الجزء من المشكلة ، نحتاج أيضًا إلى إيجاد مثل هذه الأزواج. سنحل المشكلة باستخدام البرمجة الديناميكية لأن حل هذا باستخدام العودية سيتجاوز الحدود الزمنية. علاقة التكرار تشبه إلى حد بعيد علاقة LIS (أطول زيادة في اللاحقة). سنقوم بإنشاء متجه من النواقل. سيشير كل عنصر من عناصر المتجه هذا إلى الأزواج التي تصنع أقصى تسلسل للطول عندما نختار دائمًا العنصر المقابل للعنصر الحالي في الإدخال.

لذا ، فإن علاقة التكرار هي

طباعة سلسلة الطول الأقصى للأزواج

رمز

كود C ++ لطباعة أقصى طول لسلسلة من الأزواج

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


void maxChainLength(vector<pair<int,int>> &input) 
{ 
    sort(input.begin(), input.end());
  
    int n = input.size();
    vector<vector<pair<int,int>>> dp(n); 
  	int mx = 0;
    // base case
    dp[0].push_back(input[0]); 
    for(int i=1;i<n;i++) 
    {
        for(int j=0;j<i;j++)
        {
            if ((input[j].second < input[i].first) && (dp[j].size() > dp[i].size())) // the condition must be satisfied 
                dp[i] = dp[j];
        } 
        dp[i].push_back(input[i]);
        if(dp[i].size() > dp[mx].size())
        	mx = i;
    }
    for(auto x: dp[mx])
    	cout<<"("<<x.first<<", "<<x.second<<") ";
} 

int main()
{ 
    vector<pair<int,int>> input = {{1, 2}, {10, 30}, {5, 6}, {15, 25}, {17, 21}};
    maxChainLength(input);
}
(1, 2) (5, 6) (10, 30)

كود جافا لطباعة أقصى طول لسلسلة من الأزواج

import java.util.*;

class Main{
    static void maxChainLength(ArrayList<ArrayList<Integer>> input)
    {
        Collections.sort(input, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });

        int n = input.size();
        ArrayList<ArrayList<ArrayList<Integer>>> dp = new ArrayList<ArrayList<ArrayList<Integer>>>();
        for(int i=0;i<n;i++)
            dp.add(new ArrayList<ArrayList<Integer>>());
        int mx = 0;
        // base case
        dp.get(0).add(input.get(0));
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(input.get(j).get(1) < input.get(i).get(0) && (dp.get(j).size() > dp.get(i).size())){
                    dp.set(i, new ArrayList<ArrayList<Integer>>(dp.get(j)));
                }
            }
            dp.get(i).add(input.get(i));
            if(dp.get(i).size() > dp.get(mx).size())
                mx = i;
        }
        for(ArrayList<Integer> x: dp.get(mx))
            System.out.print("("+x.get(0)+", "+x.get(1)+") ");
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> input = new ArrayList<ArrayList<Integer>>();
        input.add(new ArrayList(Arrays.asList(1, 2)));
        input.add(new ArrayList(Arrays.asList(10, 30)));
        input.add(new ArrayList(Arrays.asList(5, 6)));
        input.add(new ArrayList(Arrays.asList(15, 25)));
        input.add(new ArrayList(Arrays.asList(17, 21)));
        maxChainLength(input);
    }
}
(1, 2) (5, 6) (10, 30)

تحليل التعقيد

تعقيد الوقت

يا (N ^ 2) ، لأن المشكلة تشبه مشكلة LIS. وفي هذه المشكلة أيضًا ، استخدمنا حلقة متداخلة لإيجاد زوج سلسلة مثل إذا أضفنا الزوج الحالي. تظل الحالة راضية. وبالتالي فإن تعقيد الوقت هو متعدد الحدود.

تعقيد الفضاء

يا (N ^ 2) ، التعقيد المكاني هو أيضًا متعدد الحدود لأننا استخدمنا متجهًا للمتجهات. في أسوأ الحالات عندما يكون الحد الأقصى لطول السلسلة مساويًا لحجم الإدخال. ثم سيكون لدينا متجه من المتجهات أزواج O (N ^ 2). وبالتالي فإن المساحة المطلوبة هي أيضًا كثيرة الحدود.