Рубрики

Длинная битонная подпоследовательность | DP-15

Для данного массива arr [0… n-1], содержащего n натуральных чисел, подпоследовательность arr [] называется Bitonic, если она сначала увеличивается, а затем уменьшается. Напишите функцию, которая принимает массив в качестве аргумента и возвращает длину самой длинной битовой подпоследовательности.
Последовательность, отсортированная по возрастанию, считается битовой, а убывающая часть — пустой. Аналогично, последовательность убывающих порядков считается битовой, а возрастающая часть — пустой.

Примеры:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

Источник: Microsoft Интервью Вопрос

Решение
Эта проблема представляет собой вариант стандартной задачи с наибольшей возрастающей подпоследовательностью (LIS) . Пусть входной массив будет arr [] длины n. Нам нужно построить два массива lis [] и lds [], используя динамическое программирование для решения задачи LIS . lis [i] хранит длину самой длинной увеличивающейся подпоследовательности, заканчивающейся на arr [i]. lds [i] хранит длину самой длинной убывающей подпоследовательности, начиная с arr [i]. Наконец, нам нужно вернуть максимальное значение lis [i] + lds [i] — 1, где i от 0 до n-1.

Ниже приведена реализация вышеупомянутого решения динамического программирования.

C ++

/ * Реализация динамического программирования задачи с самой длинной битовой подпоследовательностью * /
#include<stdio.h>
#include<stdlib.h>

  
/ * lbs () возвращает длину самой длинной битовой подпоследовательности в

    обр [] размера n. Функция в основном создает два временных массива

    lis [] и lds [] и возвращает максимум lis [i] + lds [i] - 1.

  

    lis [i] ==> Самая длинная возрастающая подпоследовательность, заканчивающаяся на arr [i]

    lds [i] ==> Самая длинная убывающая подпоследовательность, начинающаяся с arr [i]

* /

int lbs( int arr[], int n )

{

   int i, j;

  

   / * Выделить память для LIS [] и инициализировать значения LIS как 1 для

      все индексы * /

   int *lis = new int[n];

   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;

  

   / * Выделить память для lds и инициализировать значения LDS для

      все индексы * /

   int *lds = new int [n];

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

      lds[i] = 1;

  

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

   for (i = n-2; i >= 0; i--)

      for (j = n-1; j > i; j--)

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

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

  

  

   / * Вернуть максимальное значение lis [i] + lds [i] - 1 * /

   int max = lis[0] + lds[0] - 1;

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

     if (lis[i] + lds[i] - 1 > max)

         max = lis[i] + lds[i] - 1;

   return max;

}

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

int main()

{

  int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,

              13, 3, 11, 7, 15};

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

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

  return 0;

}

Джава

/ * Реализация динамического программирования на Java для самой длинной битоники

   проблема подпоследовательности * /

import java.util.*;

import java.lang.*;

import java.io.*;

  

class LBS

{

    / * lbs () возвращает длину самой длинной битовой подпоследовательности в

    обр [] размера n. Функция в основном создает два временных массива

    lis [] и lds [] и возвращает максимум lis [i] + lds [i] - 1.

  

    lis [i] ==> Самая длинная возрастающая подпоследовательность, заканчивающаяся на arr [i]

    lds [i] ==> Самая длинная убывающая подпоследовательность, начинающаяся с arr [i]

    * /

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

    {

        int i, j;

  

        / * Выделить память для LIS [] и инициализировать значения LIS как 1 для

            все индексы * /

        int[] lis = new int[n];

        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;

  

        / * Выделить память для lds и инициализировать значения LDS для

            все индексы * /

        int[] lds = new int [n];

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

            lds[i] = 1;

  

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

        for (i = n-2; i >= 0; i--)

            for (j = n-1; j > i; j--)

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

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

  

  

        / * Вернуть максимальное значение lis [i] + lds [i] - 1 * /

        int max = lis[0] + lds[0] - 1;

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

            if (lis[i] + lds[i] - 1 > max)

                max = lis[i] + lds[i] - 1;

  

        return max;

    }

  

    public static void main (String[] args)

    {

        int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,

                    13, 3, 11, 7, 15};

        int n = arr.length;

        System.out.println("Length of LBS is "+ lbs( arr, n ));

    }

}

питон

# Реализация динамического программирования задачи с самой длинной битовой подпоследовательностью
«»»
lbs () возвращает длину самой длинной битовой подпоследовательности в
обр [] размера n. Функция в основном создает два временных массива
lis [] и lds [] и возвращает максимум lis [i] + lds [i] - 1.

  
lis [i] ==> Самая длинная возрастающая подпоследовательность, заканчивающаяся на arr [i]
lds [i] ==> Самая длинная убывающая подпоследовательность, начинающаяся с arr [i]
«»»

  

def lbs(arr):

    n = len(arr)

  

  

    # выделить память для LIS [] и инициализировать значения LIS как 1

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

    lis = [1 for i in range(n+1)]

  

    # Вычислить значения 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

  

    # выделить память для LDS и инициализировать значения LDS для

    # все индексы

    lds = [1 for i in range(n+1)]

      

    # Вычислить значения LDS справа налево

    for i in reversed(range(n-1)): # цикл от n-2 до 0

        for j in reversed(range(i-1 ,n)): # переход от n-1 до i-1

            if(arr[i] > arr[j] and lds[i] < lds[j] + 1):

                lds[i] = lds[j] + 1 

  

  

    # Вернуть максимальное значение (lis [i] + lds [i] - 1)

    maximum = lis[0] + lds[0] - 1

    for i in range(1 , n):

        maximum = max((lis[i] + lds[i]-1), maximum)

      

    return maximum

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

arr =  [0 , 8 , 4, 12, 2, 10 , 6 , 14 , 1 , 9 , 5 , 13,

        3, 11 , 7 , 15]

print "Length of LBS is",lbs(arr)

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

C #

/ * Реализация динамического программирования в

   C # для самой длинной проблемы битовой подпоследовательности * /

using System;

  

class LBS {

      

    / * lbs () возвращает длину самой длинной битовой подпоследовательности в

    обр [] размера n. Функция в основном создает два временных массива

    lis [] и lds [] и возвращает максимум lis [i] + lds [i] - 1.

  

    lis [i] ==> Самая длинная возрастающая подпоследовательность, заканчивающаяся на arr [i]

    lds [i] ==> Самая длинная убывающая подпоследовательность, начинающаяся с arr [i]

    * /

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

    {

        int i, j;

  

        / * Выделить память для LIS [] и инициализировать

           Значения LIS как 1 для всех индексов * /

        int[] lis = new int[n];

        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;

  

        / * Выделить память для lds и инициализировать значения LDS для

            все индексы * /

        int[] lds = new int[n];

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

            lds[i] = 1;

  

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

        for (i = n - 2; i >= 0; i--)

            for (j = n - 1; j > i; j--)

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

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

  

        / * Вернуть максимальное значение lis [i] + lds [i] - 1 * /

        int max = lis[0] + lds[0] - 1;

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

            if (lis[i] + lds[i] - 1 > max)

                max = lis[i] + lds[i] - 1;

  

        return max;

    }

      

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

    public static void Main()

    {

        int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,

                                      13, 3, 11, 7, 15 };

        int n = arr.Length;

        Console.WriteLine("Length of LBS is " + lbs(arr, n));

    }

}

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

PHP

<?php 
// Динамическое программирование реализации
// самой длинной проблемы битовой подпоследовательности

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

   Битонная подпоследовательность в arr [] размера n.

   Функция в основном создает два временных

   массивы lis [] и lds [] и возвращает

   максимальный lis [i] + lds [i] - 1.

  

   lis [i] ==> Самая длинная возрастающая подпоследовательность

              заканчивающийся на arr [i]

   lds [i] ==> Самая длинная убывающая подпоследовательность

              начиная с обр

* /

function lbs(&$arr, $n)

{

  

    / * Выделить память для LIS [] и инициализировать

       Значения LIS как 1 для всех индексов * /

    $lis = array_fill(0, $n, NULL);

    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;

      

    / * Выделить память для lds и инициализировать

       Значения LDS для всех индексов * /

    $lds = array_fill(0, $n, NULL);

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

        $lds[$i] = 1;

      

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

    for ($i = $n - 2; $i >= 0; $i--)

        for ($j = $n - 1; $j > $i; $j--)

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

                $lds[$i] < $lds[$j] + 1)

                $lds[$i] = $lds[$j] + 1;

      

    / * Вернуть максимальное значение

       lis [i] + lds [i] - 1 * /

    $max = $lis[0] + $lds[0] - 1;

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

        if ($lis[$i] + $lds[$i] - 1 > $max)

            $max = $lis[$i] + $lds[$i] - 1;

    return $max;

}

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

$arr = array(0, 8, 4, 12, 2, 10, 6, 14, 

             1, 9, 5, 13, 3, 11, 7, 15);

$n = sizeof($arr);

echo "Length of LBS is " . lbs( $arr, $n );

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


Выход:

 Length of LBS is 7

Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (n)

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

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

Длинная битонная подпоследовательность | DP-15

0.00 (0%) 0 votes