Maksimum uzunluqlu cüt zəncirini çap edin

Problem bəyanat

Problem "Çapların Maksimum Uzunluq Zəncirini Çap et" sizə bəzi cüt cütlərin verildiyini bildirir. Hər cütdə birinci rəqəmin ikinci rəqəmdən kiçik olduğu verilir. İndi ən uzun zənciri tapmalısınız ki, əvvəlki cütlüyün (a, b) ikinci sayı (c, d) cütlüyündən sonrakı ilk saydan (b <c) kiçik olsun.

misal

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

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

Izahat

Verilən cütlərin hamısı şərtləri təmin etdiyi üçün bütün cütləri seçdik.

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

(1, 2), (5, 6), (10, 30)

Izahat

Seçdiyimiz üçüncü cütün heç bir əhəmiyyəti yoxdur. Qalan üç cütdən birini seçə bilərdik, çünki hamısı şərtləri təmin edirdi. Ancaq üç qalandan heç birini seçə bilmərik.

Maksimum Uzunluqlu Cütlük Zəncirinin çapına yanaşma

Problem, maksimum uzunluqlu cüt zəncirini tapmağı və çap etməyimizi tələb edir. Yaxşı burada maksimum uzunluq nə deməkdir? Buradakı maksimum uzunluq nəticədəki cüt sayını təmsil edir. Beləliklə, sonda maksimum uzunluğu təşkil edən cütləri tapmaq lazımdır.

Artıq müzakirə etdik bu problem. Müzakirə etdiyimiz problem maksimum uzunluğu tapmağımızı istədi. Orada problemi həll etmək üçün fərqli yanaşmaları müzakirə etdik. Problemin bu hissəsində, belə cütləri tapmaq lazımdır. Problemi Dinamik Proqramlaşdırma vasitəsi ilə həll edəcəyik, çünki bunu rekursiyadan istifadə edərək həll etmək vaxt limitlərini keçəcəkdir. Təkrarlanma əlaqəsi LIS (Ən Uzun Artıran Nəticə) ilə çox oxşardır. Bir vektor vektoru yaradacağıq. Bu vektor vektorunun hər bir elementi həmişə girişdəki cari elementə uyğun element seçdiyimiz zaman maksimum uzunluq ardıcıllığını yaradan cütləri ifadə edəcəkdir.

Beləliklə, təkrarlanma əlaqəsi belədir

Kodu

Maksimum Uzunluqlu Cütlük Zəncirini Yazdırmaq üçün C ++ kodu

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

Maksimum uzunluqlu cüt zəncirini çap etmək üçün Java kodu

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)

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N ^ 2), çünki problem LIS probleminə bənzəyir. Həm də bu problemdə, cari cütü əlavə etsək, bir zəncir cütü tapmaq üçün iç içə döngədən istifadə etdik. Vəziyyət məmnun qalır. Beləliklə zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (N ^ 2), məkan mürəkkəbliyi də polinomdur, çünki vektorların vektorundan istifadə etdik. Ən pis halda, maksimum zəncir uzunluğu girişin ölçüsünə bərabərdir. O zaman vektorlarımızın vektoru O (N ^ 2) cütlüyə sahib olacaqdır. Beləliklə, tələb olunan yer çox polinomdur.