Печати Синџир на парови со максимална должина


Ниво на тешкотија Медиум
Често прашувано во Амазон
Динамичко програмирање

Изјава за проблем

Проблемот „Печати синџир на парови со максимална должина“ наведува дека ти се дадени неколку парови на броеви. Дадено е дека во секој пар, првиот број е помал од вториот број. Сега треба да го пронајдете најдолгиот ланец, така што вториот број на претходниот пар (a, b) е помал од првиот број на следниот после парот (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)

Објаснување

Третиот пар што го избравме не е важен. Можевме да избереме кој било од трите преостанати парови затоа што сите го задоволија условот. Но, не можеме да избереме ниту два од трите остатоци.

Пристап кон печатење на парови со максимална должина

Проблемот бара од нас да најдеме и отпечатиме синџир на парови со максимална должина. Значи, што значи максималната должина тука? Максималната должина тука претставува број на парови во резултатот. Значи, на крајот, треба да ги најдеме оние парови што ја сочинуваат максималната должина.

Веќе разговаравме овој проблем. Проблемот за кој разговаравме побара од нас да ја најдеме максималната должина. Таму разговаравме за различни пристапи за справување со проблемот. Овде, во овој дел од проблемот, ние исто така треба да најдеме такви парови. Ние ќе го решиме проблемот користејќи Динамичко програмирање бидејќи решавањето на ова со користење на рекурзија ќе ги надмине временските ограничувања. Релацијата на повторување е многу слична на онаа на ЛИС (најдолго растечка последица). Willе создадеме вектор на вектори. Секој елемент од овој вектор на вектори ќе ги означи паровите што ја прават низата со максимална должина кога секогаш ќе го избереме елементот што одговара на тековниот елемент во влезот.

Значи, односот на повторување е

Печати Синџир на парови со максимална должина

Код

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)

Java код за печатење на парови со максимална должина

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), бидејќи проблемот е сличен на проблемот со ЛИС. И во овој проблем, исто така, користевме вгнездена јамка за да најдеме синџир пар таков што ако го додадеме тековниот пар. Состојбата останува задоволена. Така, временската сложеност е полином.

Комплексноста на просторот

О (N ^ 2), комплексноста на просторот е исто така полиномна бидејќи користевме вектор на вектори. Во најлош случај кога максималната должина на ланецот е еднаква на големината на влезот. Тогаш нашиот вектор на вектори ќе има парови О (N ^ 2). Така, потребниот простор е исто така полином.