சோடிகளின் அதிகபட்ச நீள சங்கிலியை அச்சிடுக


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான்
டைனமிக் புரோகிராமிங்

சிக்கல் அறிக்கை

“ஜோடிகளின் அதிகபட்ச நீள சங்கிலியை அச்சிடு” என்ற சிக்கல் உங்களுக்கு சில ஜோடி எண்கள் வழங்கப்படுவதாகக் கூறுகிறது. ஒவ்வொரு ஜோடியிலும், முதல் எண் இரண்டாவது எண்ணை விட சிறியதாக இருக்கும் என்று கொடுக்கப்பட்டுள்ளது. இப்போது நீங்கள் மிக நீண்ட சங்கிலியைக் கண்டுபிடிக்க வேண்டும், அதாவது முந்தைய ஜோடியின் இரண்டாவது எண் (a, b) ஜோடி (c, d) க்குப் பிறகு அடுத்த முதல் எண்ணிக்கையை விட சிறியதாக இருக்கும் (c, d) அதாவது (b <c).

உதாரணமாக

(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)

விளக்கம்

நாங்கள் தேர்ந்தெடுத்த மூன்றாவது ஜோடி ஒரு பொருட்டல்ல. மீதமுள்ள மூன்று ஜோடிகளில் ஏதேனும் ஒன்றை நாங்கள் தேர்ந்தெடுத்திருக்கலாம், ஏனென்றால் அவை அனைத்தும் நிபந்தனையை பூர்த்தி செய்தன. ஆனால் எஞ்சியிருக்கும் மூன்றில் இரண்டையும் நாம் தேர்வு செய்ய முடியாது.

சோடிகளின் அதிகபட்ச நீள சங்கிலியை அச்சிடுவதற்கான அணுகுமுறை

ஜோடிகளின் அதிகபட்ச நீள சங்கிலியைக் கண்டுபிடித்து அச்சிட சிக்கல் கேட்கிறது. எனவே இங்கே அதிகபட்ச நீளம் என்ன? இங்கே அதிகபட்ச நீளம் முடிவின் ஜோடிகளின் எண்ணிக்கையைக் குறிக்கிறது. எனவே இறுதியில், அதிகபட்ச நீளத்தைக் கொண்ட அந்த ஜோடிகளை நாம் கண்டுபிடிக்க வேண்டும்.

நாங்கள் ஏற்கனவே விவாதித்தோம் இந்த பிரச்சனை. நாங்கள் விவாதித்த சிக்கல் அதிகபட்ச நீளத்தைக் கண்டுபிடிக்கும்படி கேட்டது. அங்கு சிக்கலைச் சமாளிக்க வெவ்வேறு அணுகுமுறைகளைப் பற்றி விவாதித்தோம். இங்கே பிரச்சினையின் இந்த பகுதியில், அத்தகைய ஜோடிகளையும் நாம் கண்டுபிடிக்க வேண்டும். டைனமிக் புரோகிராமிங்கைப் பயன்படுத்தி சிக்கலைத் தீர்ப்போம், ஏனெனில் மறுநிகழ்வைப் பயன்படுத்தி இதைத் தீர்ப்பது நேர வரம்புகளை மீறும். மறுநிகழ்வு உறவு எல்.ஐ.எஸ் (மிக நீண்ட காலமாக அதிகரிக்கும்) உடன் மிகவும் ஒத்திருக்கிறது. திசையன்களின் திசையனை உருவாக்குவோம். திசையன்களின் இந்த திசையனின் ஒவ்வொரு உறுப்பு உள்ளீடுகளில் தற்போதைய உறுப்புடன் தொடர்புடைய உறுப்பை நாம் எப்போதும் தேர்ந்தெடுக்கும்போது அதிகபட்ச நீள வரிசையை உருவாக்கும் ஜோடிகளைக் குறிக்கும்.

எனவே, மீண்டும் நிகழும் உறவு

சோடிகளின் அதிகபட்ச நீள சங்கிலியை அச்சிடுக

குறியீடு

ஜோடிகளின் அதிகபட்ச நீள சங்கிலியை அச்சிட சி ++ குறியீடு

#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)

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் ^ 2), ஏனெனில் சிக்கல் எல்.ஐ.எஸ் பிரச்சினைக்கு ஒத்ததாகும். இந்த சிக்கலில் ஒரு சங்கிலி ஜோடியைக் கண்டுபிடிக்க ஒரு உள்ளமைக்கப்பட்ட வளையத்தைப் பயன்படுத்தினோம், அதாவது தற்போதைய ஜோடியைச் சேர்த்தால். நிலை திருப்தி அளிக்கிறது. இதனால் நேர சிக்கலானது பல்லுறுப்புக்கோவை.

விண்வெளி சிக்கலானது

ஓ (என் ^ 2), திசையன் திசையனைப் பயன்படுத்தியதால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும். மிக மோசமான நிலையில், அதிகபட்ச சங்கிலி நீளம் உள்ளீட்டின் அளவிற்கு சமமாக இருக்கும்போது. எங்கள் திசையன்களின் திசையன் O (N ^ 2) ஜோடிகளைக் கொண்டிருக்கும். இதனால் தேவையான இடமும் பல்லுறுப்புக்கோவையாகும்.