Отпечатайте верига с двойки с максимална дължина


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

Декларация за проблема

Проблемът „Отпечатайте верига с двойки с максимална дължина“ гласи, че са ви дадени няколко двойки числа. Дадено е, че във всяка двойка първото число е по-малко от второто число. Сега трябва да намерите най-дългата верига, така че второто число на предходната двойка (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)

Обяснение

Третата двойка, която избрахме, няма значение. Можехме да изберем някоя от трите останали двойки, защото всички те отговаряха на условието. Но не можем да изберем нито едно от трите останки.

Подход за отпечатване на верига с двойки с максимална дължина

Проблемът ни изисква да намерим и отпечатаме веригата с двойки с максимална дължина. И така, какво означава максималната дължина тук? Максималната дължина тук представлява броя на двойките в резултата. Така че в крайна сметка трябва да намерим онези двойки, които съставляват максималната дължина.

Вече обсъдихме този проблем. Проблемът, който обсъдихме, ни помоли да намерим максималната дължина. Там обсъдихме различни подходи за справяне с проблема. Тук в тази част на проблема също трябва да намерим такива двойки. Ще разрешим проблема с помощта на динамично програмиране, защото решаването на това с помощта на рекурсия ще надхвърли ограниченията във времето. Връзката на повторяемостта е много подобна на тази на LIS (Longest Increasing Subsequence). Ще създадем вектор от вектори. Всеки елемент от този вектор на вектори ще означава двойките, които правят последователността с максимална дължина, когато винаги избираме елемента, съответстващ на текущия елемент във входа.

И така, връзката рецидив е

Отпечатайте верига с двойки с максимална дължина

код

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)

Анализ на сложността

Сложност във времето

O (N ^ 2), защото проблемът е подобен на проблема с LIS. И в този проблем също използвахме вложен цикъл, за да намерим двойка верига, така че ако добавим текущата двойка. Условието остава изпълнено. По този начин сложността на времето е многочленна.

Сложност на пространството

O (N ^ 2), сложността на пространството също е полиномна, защото сме използвали вектор на вектори. В най-лошия случай, когато максималната дължина на веригата е равна на размера на входа. Тогава нашият вектор от вектори ще има двойки O (N ^ 2). По този начин необходимото пространство също е полином.