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

01.01.2020Динамическое программирование

Для данного массива 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