Рубрики

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

Проблема самой длинной возрастающей подпоследовательности (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. Это следует за рекурсивной структурой, обсужденной выше.

# Наивная реализация 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

Выход:

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.

# Динамическое программирование 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

Выход:

Length of lis is 5

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

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

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

0.00 (0%) 0 votes