Рубрики

Программа C ++ для самой длинной возрастающей подпоследовательности

Проблема самой длинной возрастающей подпоследовательности (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}

Перекрывающиеся подзадачи:
Учитывая вышеописанную реализацию, ниже приведено дерево рекурсии для массива размера 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 / C ++ реализация задачи LIS * /
#include <stdio.h>
#include <stdlib.h>

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

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

int lis(int arr[], int n)

{

    int *lis, i, j, max = 0;

    lis = (int*)malloc(sizeof(int) * n);

  

    / * Инициализировать значения 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];

  

    / * Свободная память, чтобы избежать утечки памяти * /

    free(lis);

  

    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 %d\n", lis(arr, n));

    return 0;

}

Джава

/ * Реализация динамического программирования на Java
проблемы ЛИС * /

import java.util.*;

  

class GFG 

{

  

    / *

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

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

    * /

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

    {

        int max = 0;

        int[] lst = new int[n];

  

        // инициализируем значения LIS для всех индексов

        Arrays.fill(lst, 1);

  

        / * Вычислить оптимизированные значения LIS

        в восходящем порядке * /

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

        {

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

            {

                if (arr[i] > arr[j] && 

                    lst[i] < lst[j] + 1)

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

            }

        }

  

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

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

            if (max < lst[i])

                max = lst[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));

    }

}

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

python3

# Dyanmic Программирование python3
# реализация проблемы ЛИС

  
# lis () возвращает длину
# самая длинная возрастающая подпоследовательность
# в обр [] размера n

def lis(arr, n):

    i, j, maxm = 0, 0, 0

      

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

    lst = [1 for s in range(n)]

      

    for i in range(1, n):

        for j in range(0, i):

            if (arr[i] > arr[j] and 

                lst[i] < lst[j] + 1):

                lst[i] = lst[j] + 1

      

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

    for i in range(0, n):

        if maxm < lst[i]:

            maxm = lst[i]

      

    return maxm

  
Код водителя

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

n = len(arr)

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

  
# Этот код добавлен
# Мохит Кумар 29

Выход:

Length of lis is 5

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 3 (самая длинная возрастающая подпоследовательность) для более подробной информации!

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

Программа C ++ для самой длинной возрастающей подпоследовательности

0.00 (0%) 0 votes