Рубрики

Самая длинная общая возрастающая подпоследовательность (LCS + LIS)

Пререквизиты: LCS , LIS

Учитывая два массива, найдите длину самой длинной общей возрастающей подпоследовательности [LCIS] и напечатайте одну из таких последовательностей (может существовать несколько последовательностей)

Предположим, мы рассматриваем два массива:
arr1 [] = {3, 4, 9, 1} и
arr2 [] = {5, 3, 8, 9, 10, 2, 1}

Наш ответ будет {3, 9}, так как это самая длинная общая подпоследовательность, которая также увеличивается.

Идея состоит в том, чтобы использовать динамическое программирование и здесь. Мы храним самую длинную общую возрастающую подпоследовательность, заканчивающуюся в каждом индексе arr2 []. Мы создаем таблицу вспомогательного массива [] так, что таблица [j] хранит длину LCIS, заканчивающуюся на arr2 [j]. В конце мы возвращаем максимальное значение из этой таблицы. Для заполнения значений в этой таблице мы пересекаем все элементы arr1 [], а для каждого элемента arr1 [i] мы пересекаем все элементы arr2 []. Если мы находим совпадение, мы обновляем таблицу [j] длиной текущей LCIS. Чтобы поддерживать текущие значения LCIS, мы продолжаем проверять действительные значения таблицы [j].

Ниже приведена программа для определения длины LCIS.

C ++

// Программа на C ++ для определения длины наибольшего общего
// Увеличение подпоследовательности (LCIS)
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает длину и LCIS двух
// массивы arr1 [0..n-1] и arr2 [0..m-1]

int LCIS(int arr1[], int n, int arr2[], int m)

{

    // таблица [j] будет хранить длину LCIS

    // заканчивается arr2 [j]. Мы инициализируем его как 0,

    int table[m];

    for (int j=0; j<m; j++)

        table[j] = 0;

  

    // Обходим все элементы arr1 []

    for (int i=0; i<n; i++)

    {

        // Инициализируем текущую длину LCIS

        int current = 0;

  

        // Для каждого элемента arr1 [], пройти все

        // элементы arr2 [].

        for (int j=0; j<m; j++)

        {

            // Если оба массива имеют одинаковые элементы.

            // Обратите внимание, что мы не нарушаем цикл здесь.

            if (arr1[i] == arr2[j])

                if (current + 1 > table[j])

                    table[j] = current + 1;

  

            / * Теперь ищем предыдущее меньшее общее

               элемент для текущего элемента arr1 * /

            if (arr1[i] > arr2[j])

                if (table[j] > current)

                    current = table[j];

        }

    }

  

    // Максимальное значение в таблице [] является результатом

    int result = 0;

    for (int i=0; i<m; i++)

        if (table[i] > result)

           result = table[i];

  

    return result;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr1[] = {3, 4, 9, 1};

    int arr2[] = {5, 3, 8, 9, 10, 2, 1};

  

    int n = sizeof(arr1)/sizeof(arr1[0]);

    int m = sizeof(arr2)/sizeof(arr2[0]);

  

    cout << "Length of LCIS is "

         << LCIS(arr1, n, arr2, m);

    return (0);

}

Джава

// Java-программа для определения длины самого длинного
// Общая возрастающая подпоследовательность (LCIS)

import java.io.*;

  

class GFG {

  

    // Возвращает длину и LCIS двух

    // массивы arr1 [0..n-1] и arr2 [0..m-1]

    static int LCIS(int arr1[], int n, int arr2[],

                                         int m)

    {

        // таблица [j] будет хранить длину

        // LCIS, заканчивающийся на arr2 [j]. Инициализируем

        // это как 0,

        int table[] = new int[m];

        for (int j = 0; j < m; j++)

            table[j] = 0;

  

        // Обходим все элементы arr1 []

        for (int i = 0; i < n; i++)

        {

            // Инициализируем текущую длину LCIS

            int current = 0;

  

            // Для каждого элемента arr1 [], trvarse

            // все элементы arr2 [].

            for (int j = 0; j < m; j++)

            {

                // Если оба массива одинаковы

                // элементы. Обратите внимание, что мы не

                // разорвать цикл здесь.

                if (arr1[i] == arr2[j])

                    if (current + 1 > table[j])

                        table[j] = current + 1;

  

                / * Теперь ищем предыдущее меньшее

                общий элемент для тока

                элемент arr1 * /

                if (arr1[i] > arr2[j])

                    if (table[j] > current)

                        current = table[j];

            }

        }

  

        // Максимальное значение в таблице [] отсутствует

        // результат

        int result = 0;

        for (int i=0; i<m; i++)

            if (table[i] > result)

            result = table[i];

  

        return result;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args)

    {

        int arr1[] = {3, 4, 9, 1};

        int arr2[] = {5, 3, 8, 9, 10, 2, 1};

  

        int n = arr1.length;

        int m = arr2.length;

  

    System.out.println("Length of LCIS is " +

                       LCIS(arr1, n, arr2, m));

    }

}
// Этот код предоставлен Prerna Saini

Python 3

# Python 3 Программа для определения длины
# Самая длинная общая возрастающая подпоследовательность (LCIS)

  
# Возвращает длину и LCIS двух
# массивы arr1 [0..n-1] и arr2 [0..m-1]

def LCIS(arr1, n, arr2, m):

  

    # table [j] будет хранить длину LCIS

    # заканчивается на arr2 [j]. Мы инициализируем его как 0,

    table = [0] * m

    for j in range(m):

        table[j] = 0

  

    # Обходить все элементы arr1 []

    for i in range(n):

      

        # Инициализировать текущую длину LCIS

        current = 0

  

        # Для каждого элемента arr1 [],

        # пройти все элементы arr2 [].

        for j in range(m):

              

            # Если оба массива имеют одинаковые элементы.

            # Обратите внимание, что мы не нарушаем цикл здесь.

            if (arr1[i] == arr2[j]):

                if (current + 1 > table[j]):

                    table[j] = current + 1

  

            # Теперь ищите предыдущие меньшие общие

            # элемент для текущего элемента arr1

            if (arr1[i] > arr2[j]):

                if (table[j] > current):

                    current = table[j]

  

    # Максимальное значение в таблице []

    # вне результата

    result = 0

    for i in range(m):

        if (table[i] > result):

            result = table[i]

  

    return result

  
Код водителя

if __name__ == "__main__":

      

    arr1 = [3, 4, 9, 1]

    arr2 = [5, 3, 8, 9, 10, 2, 1]

  

    n = len(arr1)

    m = len(arr2)

  

    print("Length of LCIS is"

           LCIS(arr1, n, arr2, m))

  
# Этот код предоставлен ita_c

C #

// AC # Программа для определения длины самого длинного
// Общая возрастающая подпоследовательность (LCIS)

using System;

  

class GFG {

  

    // Возвращает длину и LCIS двух

    // массивы arr1 [0..n-1] и arr2 [0..m-1]

    static int LCIS(int []arr1, int n,

                    int []arr2, int m)

    {

        // таблица [j] будет хранить длину

        // LCIS, заканчивающийся на arr2 [j]. Инициализируем

        // это как 0,

        int []table = new int[m];

        for (int j = 0; j < m; j++)

            table[j] = 0;

  

        // Обходим все элементы arr1 []

        for (int i = 0; i < n; i++)

        {

            // Инициализируем текущую длину LCIS

            int current = 0;

  

            // Для каждого элемента arr1 [], trvarse

            // все элементы arr2 [].

            for (int j = 0; j < m; j++)

            {

                // Если оба массива одинаковы

                // элементы. Обратите внимание, что мы не

                // разорвать цикл здесь.

                if (arr1[i] == arr2[j])

                    if (current + 1 > table[j])

                        table[j] = current + 1;

  

                / * Теперь ищем предыдущее меньшее

                   общий элемент для тока

                   элемент arr1 * /

                if (arr1[i] > arr2[j])

                    if (table[j] > current)

                        current = table[j];

            }

        }

  

        // Максимальное значение в

        // таблица [] является результатом

        int result = 0;

        for (int i = 0; i < m; i++)

            if (table[i] > result)

            result = table[i];

  

        return result;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main()

    {

        int []arr1 = {3, 4, 9, 1};

        int []arr2 = {5, 3, 8, 9, 10, 2, 1};

  

        int n = arr1.Length;

        int m = arr2.Length;

  

    Console.Write("Length of LCIS is " +

                   LCIS(arr1, n, arr2, m));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа PHP для определения длины
// самое длинное общее увеличение
// подпоследовательность (LCIS)

  
// Возвращает длину и LCIS
// из двух массивов arr1 [0..n-1] и
// arr2 [0..m-1]

function LCIS($arr1, $n, $arr2, $m)

{

    // таблица [j] собирается хранить

    // длина LCIS, заканчивающаяся на

    // arr2 [j]. Мы инициализируем его как 0,

      

    $table = Array();

      

    // int table [m];

    for ($j = 0; $j < $m; $j++)

        $table[$j] = 0;

  

    // Обходим все элементы arr1 []

    for ($i = 0; $i < $n; $i++)

    {

        // Инициализируем текущий

        // длина LCIS

        $current = 0;

  

        // Для каждого элемента

        // arr1 [], trvarse all

        // элементы arr2 [].

        for ($j = 0; $j < $m; $j++)

        {

            // Если оба массива имеют

            // те же элементы. Обратите внимание, что

            // мы не нарушаем цикл здесь.

            if ($arr1[$i] == $arr2[$j])

                if ($current + 1 > $table[$j])

                    $table[$j] = $current + 1;

  

            / * Теперь ищем предыдущее меньшее

            общий элемент для тока

            элемент arr1 * /

            if ($arr1[$i] > $arr2[$j])

                if ($table[$j] > $current)

                    $current = $table[$j];

        }

    }

  

    // Максимальное значение в

    // таблица [] является результатом

    $result = 0;

    for ($i = 0; $i < $m; $i++)

        if ($table[$i] > $result)

        $result = $table[$i];

  

    return $result;

}

  
// Код драйвера

$arr1 = array (3, 4, 9, 1);

$arr2 = array (5, 3, 8, 9, 10, 2, 1);

  

$n = sizeof($arr1);

$m = sizeof($arr2);

  

echo "Length of LCIS is ",

       LCIS($arr1, $n, $arr2, $m);

  
// Этот код предоставлен ajit
?>


Выход :

Length of LCIS is 2

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Самая длинная общая возрастающая подпоследовательность (LCS + LIS)

0.00 (0%) 0 votes