Рубрики

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

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

/ * Наивная 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");

    }

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

Выход:

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.

/ * Динамическое программирование 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");

    }

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

Выход:

Length of lis is 5

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

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

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

0.00 (0%) 0 votes