Печать самой длинной битонической подпоследовательности

Опубликовано: 20 Января, 2022

Задача самой длинной битонической подпоследовательности состоит в том, чтобы найти самую длинную подпоследовательность данной последовательности, которая сначала увеличивается, а затем уменьшается. Последовательность, отсортированная в порядке возрастания, считается Bitonic, а убывающая часть - пустой. Аналогично, последовательность убывающего порядка считается Bitonic, а возрастающая часть - пустой.

Примеры:

Ввод: [1, 11, 2, 10, 4, 5, 2, 1]
Вывод: [1, 2, 10, 4, 2, 1] ИЛИ [1, 11, 10, 5, 2, 1] 
    ИЛИ [1, 2, 4, 5, 2, 1]

Ввод: [12, 11, 40, 5, 3, 1]
Вывод: [12, 11, 5, 3, 1] ИЛИ [12, 40, 5, 3, 1]

Ввод: [80, 60, 30, 40, 20, 10]
Вывод: [80, 60, 30, 20, 10] ИЛИ [80, 60, 40, 20, 10]

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

В предыдущем посте мы обсуждали проблему самой длинной битонической подпоследовательности. Однако в сообщении был описан только код, связанный с нахождением максимальной суммы возрастающей подпоследовательности, но не с построением подпоследовательности. В этом посте мы обсудим, как построить самую длинную Bitonic Subsequence.

Пусть arr [0..n-1] будет входным массивом. Мы определяем вектор LIS так, что LIS [i] сам по себе является вектором, который хранит самую длинную возрастающую подпоследовательность arr [0..i], которая заканчивается на arr [i]. Поэтому для индекса i LIS [i] можно рекурсивно записать как -

LIS[0] = {arr[O]}
LIS[i] = {Max(LIS[j])} + arr[i] where j < i and arr[j] < arr[i] 
       = arr[i], if there is no such j

Мы также определяем вектор LDS таким образом, чтобы LDS [i] сам был вектором, который хранит самую длинную убывающую подпоследовательность arr [i..n], которая начинается с arr [i]. Следовательно, для индекса i LDS [i] можно рекурсивно записать как -

LDS [n] = {arr [n]}
LDS [i] = arr [i] + {Max (LDS [j])}, где j> i и arr [j] <arr [i] 
       = arr [i], если такого j нет

Например, для массива [1 11 2 10 4 5 2 1],

LIS [0]: 1
ЛИС [1]: 1 11
ЛИС [2]: 1 2
ЛИС [3]: 1 2 10
ЛИС [4]: 1 2 4
ЛИС [5]: 1 2 4 5
ЛИС [6]: 1 2
ЛИС [7]: 1

СПД [0]: 1
СПД [1]: 11 10 5 2 1
СПД [2]: 2 1
СПД [3]: 10 5 2 1
СПД [4]: 4 2 1
СПД [5]: 5 2 1
СПД [6]: 2 1
СПД [7]: 1

Следовательно, самая длинная битовая подпоследовательность может быть

LIS [1] + LDS [1] = [1 11 10 5 2 1] ИЛИ
LIS [3] + LDS [3] = [1 2 10 5 2 1] ИЛИ
LIS [5] + LDS [5] = [1 2 4 5 2 1]

Below is the implementation of above idea –

C++

/* Dynamic Programming solution to print Longest
   Bitonic Subsequence */
#include <bits/stdc++.h>
using namespace std;
  
// Utility function to print Longest Bitonic
// Subsequence
void print(vector<int>& arr, int size)
{
    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";
}
  
// Function to construct and print Longest
// Bitonic Subsequence
void printLBS(int arr[], int n)
{
    // LIS[i] stores the length of the longest
    // increasing subsequence ending with arr[i]
    vector<vector<int>> LIS(n);
  
    // initialize LIS[0] to arr[0]
    LIS[0].push_back(arr[0]);
  
    // Compute LIS values from left to right
    for (int i = 1; i < n; i++)
    {
        // for every j less than i
        for (int j = 0; j < i; j++)
        {
            if ((arr[j] < arr[i]) &&
                (LIS[j].size() > LIS[i].size()))
                LIS[i] = LIS[j];
        }
        LIS[i].push_back(arr[i]);
    }
  
    /* LIS[i] now stores Maximum Increasing
       Subsequence of arr[0..i] that ends with
       arr[i] */
  
    // LDS[i] stores the length of the longest
    // decreasing subsequence starting with arr[i]
    vector<vector<int>> LDS(n);
  
    // initialize LDS[n-1] to arr[n-1]
    LDS[n - 1].push_back(arr[n - 1]);
  
    // Compute LDS values from right to left
    for (int i = n - 2; i >= 0; i--)
    {
        // for every j greater than i
        for (int j = n - 1; j > i; j--)
        {
            if ((arr[j] < arr[i]) &&
                (LDS[j].size() > LDS[i].size()))
                LDS[i] = LDS[j];
        }
        LDS[i].push_back(arr[i]);
    }
  
    // reverse as vector as we"re inserting at end
    for (int i = 0; i < n; i++)
        reverse(LDS[i].begin(), LDS[i].end());
  
    /* LDS[i] now stores Maximum Decreasing Subsequence
       of arr[i..n] that starts with arr[i] */
  
    int max = 0;
    int maxIndex = -1;
  
    for (int i = 0; i < n; i++)
    {
        // Find maximum value of size of LIS[i] + size
        // of LDS[i] - 1
        if (LIS[i].size() + LDS[i].size() - 1 > max)
        {
            max = LIS[i].size() + LDS[i].size() - 1;
            maxIndex = i;
        }
    }
  
    // print all but last element of LIS[maxIndex] vector
    print(LIS[maxIndex], LIS[maxIndex].size() - 1);
  
    // print all elements of LDS[maxIndex] vector
    print(LDS[maxIndex], LDS[maxIndex].size());
}
  
// Driver program
int main()
{
    int arr[] = { 1, 11, 2, 10, 4, 5, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    printLBS(arr, n);
    return 0;
}

Java

/* Dynamic Programming solution to print Longest 
Bitonic Subsequence */
import java.util.*;
  
class GFG 
{
  
    // Utility function to print Longest Bitonic
    // Subsequence
    static void print(Vector<Integer> arr, int size) 
    {
        for (int i = 0; i < size; i++)
            System.out.print(arr.elementAt(i) + " ");
    }
  
    // Function to construct and print Longest
    // Bitonic Subsequence
    static void printLBS(int[] arr, int n) 
    {
  
        // LIS[i] stores the length of the longest
        // increasing subsequence ending with arr[i]
        @SuppressWarnings("unchecked")
        Vector<Integer>[] LIS = new Vector[n];
  
        for (int i = 0; i < n; i++)
            LIS[i] = new Vector<>();
  
        // initialize LIS[0] to arr[0]
        LIS[0].add(arr[0]);
  
        // Compute LIS values from left to right
        for (int i = 1; i < n; i++) 
        {
  
            // for every j less than i
            for (int j = 0; j < i; j++) 
            {
  
                if ((arr[i] > arr[j]) && 
                     LIS[j].size() > LIS[i].size()) 
                {
                    for (int k : LIS[j])
                        if (!LIS[i].contains(k))
                            LIS[i].add(k);
                }
            }
            LIS[i].add(arr[i]);
        }
  
        /*
        * LIS[i] now stores Maximum Increasing Subsequence 
        * of arr[0..i] that ends with arr[i]
        */
  
        // LDS[i] stores the length of the longest
        // decreasing subsequence starting with arr[i]
        @SuppressWarnings("unchecked")
        Vector<Integer>[] LDS = new Vector[n];
  
        for (int i = 0; i < n; i++)
            LDS[i] = new Vector<>();
  
        // initialize LDS[n-1] to arr[n-1]
        LDS[n - 1].add(arr[n - 1]);
  
        // Compute LDS values from right to left
        for (int i = n - 2; i >= 0; i--) 
        {
  
            // for every j greater than i
            for (int j = n - 1; j > i; j--) 
            {
                if (arr[j] < arr[i] && 
                    LDS[j].size() > LDS[i].size())
                    for (int k : LDS[j])
                        if (!LDS[i].contains(k))
                            LDS[i].add(k);
            }
            LDS[i].add(arr[i]);
        }
  
        // reverse as vector as we"re inserting at end
        for (int i = 0; i < n; i++)
            Collections.reverse(LDS[i]);
  
        /*
        * LDS[i] now stores Maximum Decreasing Subsequence 
        * of arr[i..n] that starts with arr[i]
        */
        int max = 0;
        int maxIndex = -1;
        for (int i = 0; i < n; i++)
        {
  
            // Find maximum value of size of 
            // LIS[i] + size of LDS[i] - 1
            if (LIS[i].size() + LDS[i].size() - 1 > max)
            {
                max = LIS[i].size() + LDS[i].size() - 1;
                maxIndex = i;
            }
        }
  
        // print all but last element of LIS[maxIndex] vector
        print(LIS[maxIndex], LIS[maxIndex].size() - 1);
  
        // print all elements of LDS[maxIndex] vector
        print(LDS[maxIndex], LDS[maxIndex].size());
    }
  
    // Driver Code
    public static void main(String[] args) 
    {
        int[] arr = { 1, 11, 2, 10, 4, 5, 2, 1 };
        int n = arr.length;
  
        printLBS(arr, n);
    }
}
  
// This code is contributed by
// sanjeev2552

Python3

# Dynamic Programming solution to print Longest
# Bitonic Subsequence
  
  
def _print(arr: list, size: int):
    for i in range(size):
        print(arr[i], end=" ")
  
  
# Function to construct and print Longest
# Bitonic Subsequence
def printLBS(arr: list, n: int):
  
    # LIS[i] stores the length of the longest
    # increasing subsequence ending with arr[i]
    LIS = [0] * n
    for i in range(n):
        LIS[i] = []
  
    # initialize LIS[0] to arr[0]
    LIS[0].append(arr[0])
  
    # Compute LIS values from left to right
    for i in range(1, n):
  
        # for every j less than i
        for j in range(i):
  
            if ((arr[j] < arr[i]) and (len(LIS[j]) > len(LIS[i]))):
                LIS[i] = LIS[j].copy()
  
        LIS[i].append(arr[i])
  
    # LIS[i] now stores Maximum Increasing
    # Subsequence of arr[0..i] that ends with
    # arr[i]
  
    # LDS[i] stores the length of the longest
    # decreasing subsequence starting with arr[i]
    LDS = [0] * n
    for i in range(n):
        LDS[i] = []
  
    # initialize LDS[n-1] to arr[n-1]
    LDS[n - 1].append(arr[n - 1])
  
    # Compute LDS values from right to left
    for i in range(n - 2, -1, -1):
  
        # for every j greater than i
        for j in range(n - 1, i, -1):
  
            if ((arr[j] < arr[i]) and (len(LDS[j]) > len(LDS[i]))):
                LDS[i] = LDS[j].copy()
  
        LDS[i].append(arr[i])
  
    # reverse as vector as we"re inserting at end
    for i in range(n):
        LDS[i] = list(reversed(LDS[i]))
  
    # LDS[i] now stores Maximum Decreasing Subsequence
    # of arr[i..n] that starts with arr[i]
  
    max = 0
    maxIndex = -1
  
    for i in range(n):
  
        # Find maximum value of size of LIS[i] + size
        # of LDS[i] - 1
        if (len(LIS[i]) + len(LDS[i]) - 1 > max):
  
            max = len(LIS[i]) + len(LDS[i]) - 1
            maxIndex = i
  
    # print all but last element of LIS[maxIndex] vector
    _print(LIS[maxIndex], len(LIS[maxIndex]) - 1)
  
    # print all elements of LDS[maxIndex] vector
    _print(LDS[maxIndex], len(LDS[maxIndex]))
  
  
# Driver Code
if __name__ == "__main__":
  
    arr = [1, 11, 2, 10, 4, 5, 2, 1]
    n = len(arr)
  
    printLBS(arr, n)
  

                    
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИ
                                    