Друк ланцюжка пар максимальної довжини


Рівень складності Medium
Часто запитують у Амазонка
Динамічне програмування

Постановка проблеми

У проблемі “Друк ланцюжка пар максимальної довжини” зазначено, що вам дано кілька пар чисел. Дано, що в кожній парі перше число менше другого. Тепер вам потрібно знайти найдовший ланцюжок, щоб друге число попередньої пари (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 (Найдовша зростаюча послідовність). Створимо вектор векторів. Кожен елемент цього вектора векторів позначатиме пари, які складають послідовність максимальної довжини, коли ми завжди вибираємо елемент, що відповідає поточному елементу на вході.

Отже, відношення рецидиву є

Друк ланцюжка пар максимальної довжини

код

Код С ++ для друку ланцюжка пар максимальної довжини

#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). Таким чином, необхідний простір також є поліномом.