Рубрики

Длинная возрастающая подпоследовательность | ДП-3

Мы обсудили перекрывающиеся подзадачи и оптимальные свойства подструктуры .

Давайте обсудим проблему Longest возрастающей подпоследовательности (LIS) в качестве примера проблемы, которая может быть решена с помощью динамического программирования.
Проблема самой длинной возрастающей подпоследовательности (LIS) состоит в том, чтобы найти длину самой длинной подпоследовательности данной последовательности так, чтобы все элементы подпоследовательности сортировались в возрастающем порядке. Например, длина LIS для {10, 22, 9, 33, 21, 50, 41, 60, 80} составляет 6, а LIS составляет {10, 22, 33, 50, 60, 80}.

Больше примеров:

Input  : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20

Input  : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}

Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}

Оптимальная подструктура:
Пусть arr [0..n-1] будет входным массивом, а L (i) будет длиной LIS, заканчивающейся индексом i, так что arr [i] является последним элементом LIS.
Тогда L (i) можно записать рекурсивно как:
L (i) = 1 + max (L (j)), где 0 <j <i и arr [j] <arr [i]; или
L (i) = 1, если такого j не существует.
Чтобы найти LIS для данного массива, нам нужно вернуть max (L (i)), где 0 <i <n.
Таким образом, мы видим, что задача LIS удовлетворяет оптимальному свойству субструктуры, поскольку основная проблема может быть решена с использованием решений подзадач.

Ниже приводится простая рекурсивная реализация проблемы LIS. Это следует за рекурсивной структурой, обсужденной выше.

C / C ++

/ * Наивная C / C ++ рекурсивная реализация проблемы LIS * /
#include<stdio.h>
#include<stdlib.h>

  
/ * Чтобы использовать рекурсивные вызовы, эта функция должна возвращать

   две вещи:

   1) Длина LIS, заканчивающаяся элементом arr [n-1]. Мы используем

      max_ending_ здесь для этой цели

   2) Общий максимум, поскольку LIS может заканчиваться элементом

      прежде чем arr [n-1] max_ref используется для этой цели.

   Значение LIS полного массива размера n хранится в

   * max_ref, который является нашим окончательным результатом * /

int _lis( int arr[], int n, int *max_ref)

{

    /* Базовый вариант */

    if (n == 1)

        return 1;

  

    // 'max_ending_here' - длина LIS, заканчивающаяся на arr [n-1]

    int res, max_ending_here = 1; 

  

    / * Рекурсивно получить все LIS, заканчивающиеся на arr [0], arr [1] ...

       обр [п-2]. Если arr [i-1] меньше, чем arr [n-1], и

       max, заканчивающийся на arr [n-1], должен быть обновлен, затем

       обновить его * /

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

    {

        res = _lis(arr, i, max_ref);

        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)

            max_ending_here = res + 1;

    }

  

    // Сравнить max_ending_here с общим макс. И

    // обновляем общий максимум при необходимости

    if (*max_ref < max_ending_here)

       *max_ref = max_ending_here;

  

    // Возвращаем длину LIS, заканчивающуюся на arr [n-1]

    return max_ending_here;

}

  
// Функция-обертка для _lis ()

int lis(int arr[], int n)

{

    // переменная max содержит результат

    int max = 1;

  

    // Функция _lis () сохраняет свой результат в max

    _lis( arr, n, &max );

  

    // возвращает максимум

    return max;

}

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

int main()

{

    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

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

    printf("Length of lis is %dn",

           lis( arr, n ));

    return 0;

}

Джава

/ * Наивная Java-программа для реализации LIS * /

class LIS

{

   static int max_ref; // сохраняет LIS

  

   / * Чтобы использовать рекурсивные вызовы, эта функция должна возвращать

   две вещи:

   1) Длина LIS, заканчивающаяся элементом arr [n-1]. Мы используем

      max_ending_ здесь для этой цели

   2) Общий максимум, поскольку LIS может заканчиваться элементом

      прежде чем arr [n-1] max_ref используется для этой цели.

   Значение LIS полного массива размера n хранится в

   * max_ref, который является нашим окончательным результатом * /

   static int _lis(int arr[], int n)

   {

       // базовый вариант

       if (n == 1)

           return 1;

  

       // 'max_ending_here' - длина LIS, заканчивающаяся на arr [n-1]

       int res, max_ending_here = 1;

  

        / * Рекурсивно получить все LIS, заканчивающиеся на arr [0], arr [1] ...

           обр [п-2]. Если arr [i-1] меньше, чем arr [n-1], и

           max, заканчивающийся на arr [n-1], должен быть обновлен, затем

           обновить его * /

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

        {

            res = _lis(arr, i);

            if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)

                max_ending_here = res + 1;

        }

  

        // Сравнить max_ending_here с общим макс. И

        // обновляем общий максимум при необходимости

        if (max_ref < max_ending_here)

           max_ref = max_ending_here;

  

        // Возвращаем длину LIS, заканчивающуюся на arr [n-1]

        return max_ending_here;

   }

  

    // Функция-обертка для _lis ()

    static int lis(int arr[], int n)

    {

        // переменная max содержит результат

         max_ref = 1;

  

        // Функция _lis () сохраняет свой результат в max

        _lis( arr, n);

  

        // возвращает максимум

        return max_ref;

    }

  

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

    public static void main(String args[])

    {

        int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

        int n = arr.length;

        System.out.println("Length of lis is "

                           + lis(arr, n) + "\n");

    }

 }

/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Наивная реализация Python проблемы LIS

  
"" "Чтобы использовать рекурсивные вызовы, эта функция должна возвращать

 две вещи:

 1) Длина LIS, заканчивающаяся элементом arr [n-1]. Мы используем

 max_ending_ здесь для этой цели

 2) Общий максимум, поскольку LIS может заканчиваться элементом

 прежде чем arr [n-1] max_ref используется для этой цели.

 Значение LIS полного массива размера n хранится в

 * max_ref, который является нашим конечным результатом "" "

  
# глобальная переменная для хранения максимума

global maximum

  

def _lis(arr , n ):

  

    # разрешить доступ к глобальной переменной

    global maximum

  

    # Базовый вариант

    if n == 1 :

        return 1

  

    # maxEndingHere - длина LIS, заканчивающаяся на arr [n-1]

    maxEndingHere = 1

  

    "" "Рекурсивно получить все LIS, заканчивающиеся на arr [0], arr [1] .. arr [n-2]

       IF arr [n-1] меньше, чем arr [n-1], и max заканчивается на

       arr [n-1] необходимо обновить, затем обновить его "" "

    for i in xrange(1, n):

        res = _lis(arr , i)

        if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:

            maxEndingHere = res +1

  

    # Сравните maxEndingHere с общим максимумом. И

    # обновить общий максимум при необходимости

    maximum = max(maximum , maxEndingHere)

  

    return maxEndingHere

  

def lis(arr):

  

    # разрешить доступ к глобальной переменной

    global maximum

  

    # длина обр

    n = len(arr)

  

    Максимальная переменная содержит результат

    maximum = 1

  

    # Функция _lis () максимально сохраняет свой результат

    _lis(arr , n)

  

    return maximum

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

arr = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60]

n = len(arr)

print "Length of lis is ", lis(arr)

  
# Этот код предоставлен NIKHIL KUMAR SINGH

C #

using System;

  
/ * Наивная программа C # для внедрения LIS * /

class LIS

{

   static int max_ref; // сохраняет LIS

   

   / * Чтобы использовать рекурсивные вызовы, эта функция должна возвращать

   две вещи:

   1) Длина LIS, заканчивающаяся элементом arr [n-1]. Мы используем

      max_ending_ здесь для этой цели

   2) Общий максимум, поскольку LIS может заканчиваться элементом

      прежде чем arr [n-1] max_ref используется для этой цели.

   Значение LIS полного массива размера n хранится в

   * max_ref, который является нашим окончательным результатом * /

   static int _lis(int[] arr, int n)

   {

       // базовый вариант

       if (n == 1)

           return 1;

   

       // 'max_ending_here' - длина LIS, заканчивающаяся на arr [n-1]

       int res, max_ending_here = 1;

   

        / * Рекурсивно получить все LIS, заканчивающиеся на arr [0], arr [1] ...

           обр [п-2]. Если arr [i-1] меньше, чем arr [n-1], и

           max, заканчивающийся на arr [n-1], должен быть обновлен, затем

           обновить его * /

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

        {

            res = _lis(arr, i);

            if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)

                max_ending_here = res + 1;

        }

   

        // Сравнить max_ending_here с общим макс. И

        // обновляем общий максимум при необходимости

        if (max_ref < max_ending_here)

           max_ref = max_ending_here;

   

        // Возвращаем длину LIS, заканчивающуюся на arr [n-1]

        return max_ending_here;

   }

   

    // Функция-обертка для _lis ()

    static int lis(int[] arr, int n)

    {

        // переменная max содержит результат

         max_ref = 1;

   

        // Функция _lis () сохраняет свой результат в max

        _lis( arr, n);

   

        // возвращает максимум

        return max_ref;

    }

   

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

    public static void Main()

    {

        int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };

        int n = arr.Length;

        Console.Write("Length of lis is "

                           + lis(arr, n) + "\n");

    }

 }

Length of lis is 5

Перекрывающиеся подзадачи:
Учитывая вышеописанную реализацию, ниже приведено дерево рекурсии для массива размера 4. lis (n) дает нам длину LIS для arr [].

              lis(4)
        /        |     
      lis(3)    lis(2)   lis(1)
     /           /
   lis(2) lis(1) lis(1)
   /
lis(1)

Мы видим, что есть много подзадач, которые решаются снова и снова. Таким образом, эта проблема имеет свойство «Перекрывающаяся подструктура», и повторного вычисления тех же подзадач можно избежать, используя Memoization или Tabulation. Ниже приведена табличная реализация проблемы LIS.

C ++

/ * Динамическое программирование C ++ реализация проблемы LIS * /
#include<bits/stdc++.h> 

using namespace std;

    
/ * lis () возвращает длину самого длинного возрастающего

  подпоследовательность в arr [] размера n * /

int lis( int arr[], int n ) 

    int lis[n];

   

    lis[0] = 1;   

  

    / * Рассчитать оптимизированные значения LIS снизу вверх * /

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

    {

        lis[i] = 1;

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

            if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) 

                lis[i] = lis[j] + 1; 

    }

  

    // Возвращаем максимальное значение в lis []

    return *max_element(lis, lis+n);

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

int main() 

    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 

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

    printf("Length of lis is %d\n", lis( arr, n ) ); 

    return 0; 

}

Джава

/ * Динамическое программирование Java реализация проблемы LIS * /

  

class LIS

{

    / * lis () возвращает длину самого длинного возрастающего

       подпоследовательность в arr [] размера n * /

    static int lis(int arr[],int n)

    {

          int lis[] = new int[n];

          int i,j,max = 0;

  

          / * Инициализировать значения LIS для всех индексов * /

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

              lis[i] = 1;

  

           / * Рассчитать оптимизированные значения LIS снизу вверх * /

           for ( i = 1; i < n; i++ )

              for ( j = 0; j < i; j++ ) 

                         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)

                    lis[i] = lis[j] + 1;

  

           / * Выберите максимум всех значений LIS * /

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

              if ( max < lis[i] )

                 max = lis[i];

  

            return max;

    }

  

    public static void main(String args[])

    {

        int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

            int n = arr.length;

            System.out.println("Length of lis is " + lis( arr, n ) + "\n" );

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Динамическое программирование Python реализация задачи LIS

  
# lis возвращает длину самой длинной увеличивающейся подпоследовательности
# в размере размера n

def lis(arr):

    n = len(arr)

  

    # Объявить список (массив) для LIS и инициализировать LIS

    # значения для всех индексов

    lis = [1]*n

  

    # Вычислить оптимизированные значения LIS снизу вверх

    for i in range (1 , n):

        for j in range(0 , i):

            if arr[i] > arr[j] and lis[i]< lis[j] + 1 :

                lis[i] = lis[j]+1

  

    # Инициализировать максимум до 0, чтобы получить максимум из всех

    # LIS

    maximum = 0

  

    # Выберите максимум всех значений LIS

    for i in range(n):

        maximum = max(maximum , lis[i])

  

    return maximum

# конец функции lis

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

arr = [10, 22, 9, 33, 21, 50, 41, 60]

print "Length of lis is", lis(arr)

# Этот код предоставлен Nikhil Kumar Singh

C #

/ * Динамическое программирование на C # реализации задачи LIS * /

  

using System ;

class LIS 

    / * lis () возвращает длину самого длинного возрастающего

    подпоследовательность в arr [] размера n * /

    static int lis(int []arr,int n) 

    

        int []lis = new int[n]; 

        int i,j,max = 0; 

  

        / * Инициализировать значения LIS для всех индексов * /

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

            lis[i] = 1; 

  

        / * Рассчитать оптимизированные значения LIS снизу вверх * /

        for ( i = 1; i < n; i++ ) 

            for ( j = 0; j < i; j++ ) 

                        if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) 

                    lis[i] = lis[j] + 1; 

  

        / * Выберите максимум всех значений LIS * /

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

            if ( max < lis[i] ) 

                max = lis[i]; 

  

            return max; 

    

  

    public static void Main() 

    

        int []arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; 

            int n = arr.Length; 

            Console.WriteLine("Length of lis is " + lis( arr, n ) + "\n" ); 

    

  

    // Этот код предоставлен Ryuga

}


Выход:

Length of lis is 5

Обратите внимание, что временная сложность вышеупомянутого решения динамического программирования (DP) составляет O (n ^ 2), и существует решение O (nLogn) для задачи LIS. Мы не обсуждали решение O (n Log n) здесь, так как цель этого поста — объяснить динамическое программирование на простом примере. Смотрите ниже сообщение для O (n Log n) решение.

Самый длинный увеличивающийся размер подпоследовательности (N log N)

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

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

Длинная возрастающая подпоследовательность | ДП-3

0.00 (0%) 0 votes