Subsecuencia bitónica más larga en O (n log n)

Dada una array arr[0 … n-1] que contiene n enteros positivos, una subsecuencia de arr[] se llama bitónica si primero es creciente y luego decreciente. Escriba una función que tome una array como argumento y devuelva la longitud de la subsecuencia bitónica más larga. 

Una secuencia ordenada en orden creciente se considera bitónica con la parte decreciente vacía. De manera similar, la secuencia de orden decreciente se considera bitónica con la parte creciente como vacía.
Complejidad de tiempo esperada: O (n log n)

Ejemplos: 

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

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

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

Hemos discutido la solución O(n 2 ) en Programación Dinámica | Conjunto 15 (Subsecuencia bitónica más larga)
La idea es seguir el tamaño de la subsecuencia creciente más larga (n log n) para ver la forma en que se calcula la longitud de la subsecuencia creciente más larga (LIS).

Algoritmo: 

Step 1: Define 4 Auxiliary arrays of size n:
        increasing[n] to calculate LIS of the 
        array  tail1[n] to store the values for 
        LIS for increasing[n]
        decreasing[n] to calculate LIS of the 
        array  tail2[n] to store the values for
        LIS for decreasing[n]
Step 2: Find LIS for increasing array
Step 3: Reverse array and store it in decreasing
Step 4: Find LIS for decreasing array
Step 5: Longest Bitonicc SubSequence length now 
        will be max of tail1[i] + tail2[i] + 1

Implementación:

C++

// C++ program to find length of longest
// Bitonic subsequence in O (n Log n( time,
#include <bits/stdc++.h>
using namespace std;
 
// Binary Search
int ceilIndex(int arr[], int l, int r, int x)
{
    if (l > r)
        return -1;
 
    int mid = l + (r - l) / 2;
    if (arr[mid] == x)
        return mid;
 
    if (x < arr[mid])
        return ceilIndex(arr, l, mid - 1, x);
 
    return ceilIndex(arr, mid + 1, r, x);
 
}
 
// function to reverse an array
void revereseArr(int arr[], int n)
{
    int i = 0;
    int j = n - 1;
    while (i < j)
       swap(arr[i++], arr[j--]);
}
 
// Returns length of longest Bitonic
// subsequence in O(n Log n) time.
int getLBSLengthLogn(int arr[], int n)
{
    // Base Case:
    if (n == 0)
        return 0;
 
 
    // Aux array storing the input array
    // in same order to calculate LIS:
    int increasing[n];
    int tail1[n];  // To store lengths of IS
 
    // Aux array storing the input array
    // in reverse order to calculate LIS:
    // This will calculate Longest Decreasing
    // Subsequence which is required for
    // Longest Bitonic Subsequence
    int decreasing[n];
    int tail2[n]; // To store lengths of DS
 
 
    // initializing first index same as
    // original array:
    increasing[0] = arr[0];
 
    // index in initialized as 1 from where
    // the remaining computations will be done
    int in = 1;
 
    // tail1 stores Longest Increasing subsequence
    // length values till index in
    tail1[0] = 0;
 
    // remaining computations to get the
    // LIS length for increasing
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < increasing[0])
        {
            increasing[0] = arr[i];
            tail1[i] = 0;
        }
        else if (arr[i] > increasing[in - 1])
        {
            increasing[in++] = arr[i];
            tail1[i] = in - 1;
        }
        else
        {
            increasing[ceilIndex(increasing, -1,
                        in - 1, arr[i])] = arr[i];
            tail1[i] = ceilIndex(increasing, -1,
                                   in - 1, arr[i]);
        }
    }
 
    // reiitializing the index to 1
    in = 1;
 
    // reversing the array to get the Longest
    // Decreasing Subsequence Length:
    revereseArr(arr, n);
    decreasing[0] = arr[0];
    tail2[0] = 0;
 
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < decreasing[0])
        {
            decreasing[0] = arr[i];
            tail2[i] = 0;
        }
        else if (arr[i] > decreasing[in - 1])
        {
            decreasing[in++] = arr[i];
            tail2[i] = in - 1;
        }
        else
        {
            decreasing[ceilIndex(decreasing, -1,
                      in - 1, arr[i])] = arr[i];
            tail2[i] = ceilIndex(decreasing, -1,
                                 in - 1, arr[i]);
        }
    }
 
    revereseArr(arr, n);
    revereseArr(tail2, n);
 
    // Longest Bitonic Subsequence length is
    // maximum of tail1[i] + tail2[i] + 1:
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (ans < (tail1[i] + tail2[i] + 1))
            ans = (tail1[i] + tail2[i] + 1);
 
 
    return ans;
}
 
// Driver code
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]);
    cout << getLBSLengthLogn(arr, n) << endl;
    return 0;
}

Java

// Java program to find length of longest
// Bitonic subsequence in O (n Log n) time,
import java.util.Arrays;
public class GFG
{
    // function to reverse an array
    static void revereseArr(int arr[])
    {
        int i = 0;
        int j = arr.length - 1;
        while (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;j--;
        }
    }
     
    // Returns length of longest Bitonic
    // subsequence in O(n Log n) time.
    static int getLBSLengthLogn(int arr[])
    {
        int n = arr.length;
         
        // Base Case:
        if(n==0)
            return 0;
         
        /*Aux array storing the input array
        in same order to calculate LIS:*/
        int increasing[] = new int[n];
         
        //to store lengths of IS
        int tail1[] = new int[n];
         
        /*Aux array storing the input array
          in reverse order to calculate LIS:
          This will calculate Longest Decreasing
          Subsequence which is required for
          Longest Bitonic Subsequence*/
        int decreasing[] = new int[n];
         
        // To store lengths of DS
        int tail2[] = new int[n];
         
        // initializing first index same as
        // original array:
        increasing[0] = arr[0];
         
        // index in initialized as 1 from where
        // the remaining computations will be done
        int in = 1;
         
        // tail1 stores Longest Increasing
        // subsequence length values till index in
        tail1[0] = 0;
         
        // remaining computations to get the
        // LIS length for increasing
        for(int i = 1; i < n; i++)
        {
            if(arr[i] < increasing[0])
            {
                increasing[0] = arr[i];
                tail1[i] = 0;
            }
            else if(arr[i] > increasing[in - 1])
            {
                increasing[in++] = arr[i];
                tail1[i] = in - 1;
            }
            else
            {
                int getIndex1 = Arrays.binarySearch(increasing,
                                                0, in, arr[i]);
                if(getIndex1 <= -1)
                    continue;
                 
                increasing[getIndex1] = arr[i];
                tail1[i] = getIndex1;
            }
        }
 
        // reinitializing the index to 1
        in = 1;
         
        // reversing the array to get the Longest
        // Decreasing Subsequence Length:
        revereseArr(arr);
        decreasing[0] = arr[0];
        tail2[0] = 0;
         
        for(int i = 0; i < n; i++)
        {
            if(arr[i] < decreasing[0])
            {
                decreasing[0] = arr[i];
                tail2[i] = 0;
            }
            else if(arr[i] > decreasing[in - 1])
            {
                decreasing[in++] = arr[i];
                tail2[i] = in - 1;
            }
            else
            {
                int getIndex2 =  Arrays.binarySearch(decreasing,
                                                0, in , arr[i]);
                if(getIndex2 <= -1)
                    continue;
             
                decreasing[getIndex2] = arr[i];
                tail2[i] = getIndex2;
             
            }
        }
         
        revereseArr(arr);
        revereseArr(tail2);
      
        // Longest Bitonic Subsequence length is
        // maximum of tail1[i] + tail2[i] + 1:
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (ans < (tail1[i] + tail2[i] + 1))
                ans = (tail1[i] + tail2[i] + 1);
        }
        return ans;
    }
 
    // Driver code to test above methods
    public static void main(String[] args)
    {
        int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14,
                      1, 9, 5, 13, 3, 11, 7, 15 };
        System.out.println(getLBSLengthLogn(arr));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 program to find length of longest
# Bitonic subsequence in O (n Log n) time
  
# Binary Search
def ceilIndex(arr, l, r, x):
    if (l > r):
        return -1
     
    mid = l + (r - l) // 2
    if (arr[mid] == x):
        return mid
     
    if (x < arr[mid]):
        return ceilIndex(arr, l, mid - 1, x)
     
    return ceilIndex(arr, mid + 1, r, x)
     
# Function to reverse an array
def revereseArr(arr, n):
    i = 0
    j = n - 1
    while (i < j):
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
        i += 1
        j -= 1
        
# Returns length of longest Bitonic
# subsequence in O(n Log n) time.
def getLBSLengthLogn(arr, n):
     
    # Base Case:
    if (n == 0):
        return 0
     
    # Aux array storing the input array
    # in same order to calculate LIS:
    increasing = [0 for i in range(n)]
    tail1 = [0 for i in range(n)]  # To store lengths of LIS
  
    # Aux array storing the input array
    # in reverse order to calculate LIS:
    # This will calculate Longest Decreasing
    # Subsequence which is required for
    # Longest Bitonic Subsequence
    decreasing = [0 for i in range(n)]
    tail2 = [0 for i in range(n)]   # To store lengths of DS
     
    # initializing first index same as
    # original array:
    increasing [0] = arr [0]
  
    # index in initialized as 1 from where
    # the remaining computations will be done
    ind = 1
     
    # tail1 stores Longest Increasing subsequence
    # length values till index in
    tail1[0] = 0
     
    # remaining computations to get the
    # LIS length for increasing
    for i in range(1, n):
        if (arr[i] < increasing[0]):
            increasing[0] = arr[i]
            tail1[i] = 0
        else if (arr[i] > increasing[ind - 1]):
            increasing[ind] = arr[i]
            ind += 1
            tail1[i] = ind - 1
        else:
            increasing[ceilIndex(increasing, -1,
                        ind - 1, arr[i])] = arr[i]
            tail1[i] = ceilIndex(increasing, -1,
                                   ind- 1, arr[i])
  
    # reinitializing the index to 1
    ind = 1
 
    # reversing the array to get the Longest
    # Decreasing Subsequence Length:
    revereseArr(arr, n)
    decreasing[0] = arr[0]
    tail2[0] = 0
    for i in range(1, n):
        if (arr[i] < decreasing[0]):
            decreasing[0] = arr[i]
            tail2[i] = 0
        else if (arr[i] > decreasing[ind - 1]):
            decreasing[ind] = arr[i]
            ind += 1
            tail2[i] = ind - 1
        else:
            decreasing[ceilIndex(decreasing, -1,
                      ind - 1, arr[i])] = arr[i]
            tail2[i] = ceilIndex(decreasing, -1,
                                 ind - 1, arr[i])
    revereseArr(arr, n)
    revereseArr(tail2, n)
    # Longest Bitonic Subsequence length is
    # maximum of tail1[i] + tail2[i] + 1:
    ans = 0
    for i in range(n):
        if (ans < (tail1[i] + tail2[i] + 1)):
            ans = (tail1[i] + tail2[i] + 1)
     
    return ans
     
# Driver code
arr = [ 0, 8, 4, 12, 2, 10, 6, 14,
                  1, 9, 5, 13, 3, 11, 7, 15]
n = len(arr)
print (getLBSLengthLogn(arr, n))
 
# This code is contributed by Sachin Bisht

C#

// C# program to find length of longest
// Bitonic subsequence in O (n Log n) time,
using System;
 
public class GFG {
     
    // function to reverse an array
    static void revereseArr(int []arr)
    {
        int i = 0;
        int j = arr.Length - 1;
        while (i < j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
     
    // Returns length of longest Bitonic
    // subsequence in O(n Log n) time.
    static int getLBSLengthLogn(int []arr)
    {
        int n = arr.Length;
         
        // Base Case:
        if(n == 0)
            return 0;
         
        /*Aux array storing the input array
        in same order to calculate LIS:*/
        int []increasing = new int[n];
         
        //to store lengths of IS
        int []tail1 = new int[n];
         
        /*Aux array storing the input array
        in reverse order to calculate LIS:
        This will calculate Longest Decreasing
        Subsequence which is required for
        Longest Bitonic Subsequence*/
        int []decreasing = new int[n];
         
        // To store lengths of DS
        int []tail2 = new int[n];
         
        // initializing first index same as
        // original array:
        increasing[0] = arr[0];
         
        // index in initialized as 1 from where
        // the remaining computations will be done
        int inn = 1;
         
        // tail1 stores Longest Increasing
        // subsequence length values till index in
        tail1[0] = 0;
         
        // remaining computations to get the
        // LIS length for increasing
        for(int i = 1; i < n; i++)
        {
            if(arr[i] < increasing[0])
            {
                increasing[0] = arr[i];
                tail1[i] = 0;
            }
            else if(arr[i] > increasing[inn - 1])
            {
                increasing[inn++] = arr[i];
                tail1[i] = inn - 1;
            }
            else
            {
                int getIndex1 = Array.BinarySearch(increasing,
                                                0, inn, arr[i]);
                if(getIndex1 <= -1)
                    continue;
                 
                increasing[getIndex1] = arr[i];
                tail1[i] = getIndex1;
            }
        }
 
        // reinitializing the index to 1
        inn = 1;
         
        // reversing the array to get the Longest
        // Decreasing Subsequence Length:
        revereseArr(arr);
        decreasing[0] = arr[0];
        tail2[0] = 0;
         
        for(int i = 0; i < n; i++)
        {
            if(arr[i] < decreasing[0])
            {
                decreasing[0] = arr[i];
                tail2[i] = 0;
            }
            else if(arr[i] > decreasing[inn - 1])
            {
                decreasing[inn++] = arr[i];
                tail2[i] = inn - 1;
            }
            else
            {
                int getIndex2 = Array.BinarySearch(decreasing,
                                             0, inn , arr[i]);
                if(getIndex2 <= -1)
                    continue;
             
                decreasing[getIndex2] = arr[i];
                tail2[i] = getIndex2;
             
            }
        }
         
        revereseArr(arr);
        revereseArr(tail2);
     
        // Longest Bitonic Subsequence length is
        // maximum of tail1[i] + tail2[i] + 1:
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (ans < (tail1[i] + tail2[i] + 1))
                ans = (tail1[i] + tail2[i] + 1);
        }
        return ans;
    }
 
    // Driver code to test above methods
    public static void Main()
    {
        int []arr = { 0, 8, 4, 12, 2, 10, 6, 14,
                     1, 9, 5, 13, 3, 11, 7, 15 };
        Console.Write(getLBSLengthLogn(arr));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find length of longest
// Bitonic subsequence in O (n Log n( time,
 
// Binary Search
function ceilIndex(&$arr, $l, $r, $x)
{
    if ($l > $r)
        return -1;
 
    $mid = intval($l + ($r - $l) / 2);
    if ($arr[$mid] == $x)
        return $mid;
 
    if ($x < $arr[$mid])
        return ceilIndex($arr, $l,
                         $mid - 1, $x);
 
    return ceilIndex($arr, $mid + 1, $r, $x);
}
 
// function to reverse an array
function revereseArr(&$arr, $n)
{
    $i = 0;
    $j = $n - 1;
    while ($i < $j)
    {
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
        $i++;
        $j--;
    }
}
 
// Returns length of longest Bitonic
// subsequence in O(n Log n) time.
function getLBSLengthLogn(&$arr, $n)
{
    // Base Case:
    if ($n == 0)
        return 0;
 
    // Aux array storing the input array
    // in same order to calculate LIS:
    $increasing = array_fill(0, $n, NULL);
    $tail1 = array_fill(0, $n, NULL); // To store lengths of IS
 
    // Aux array storing the input array
    // in reverse order to calculate LIS:
    // This will calculate Longest Decreasing
    // Subsequence which is required for
    // Longest Bitonic Subsequence
    $decreasing = array_fill(0, $n, NULL);
    $tail2 = array_fill(0, $n, NULL); // To store lengths of DS
 
    // initializing first index same as
    // original array:
    $increasing[0] = $arr[0];
 
    // index in initialized as 1 from where
    // the remaining computations will be done
    $in = 1;
 
    // tail1 stores Longest Increasing
    // subsequence length values till index in
    $tail1[0] = 0;
 
    // remaining computations to get the
    // LIS length for increasing
    for ($i = 1; $i < $n; $i++)
    {
        if ($arr[$i] < $increasing[0])
        {
            $increasing[0] = $arr[$i];
            $tail1[$i] = 0;
        }
        else if ($arr[$i] > $increasing[$in - 1])
        {
            $increasing[$in++] = $arr[$i];
            $tail1[$i] = $in - 1;
        }
        else
        {
            $increasing[ceilIndex($increasing, -1,
                        $in - 1, $arr[$i])] = $arr[$i];
            $tail1[$i] = ceilIndex($increasing, -1,
                                   $in - 1, $arr[$i]);
        }
    }
 
    // reiitializing the index to 1
    $in = 1;
 
    // reversing the array to get the Longest
    // Decreasing Subsequence Length:
    revereseArr($arr, $n);
    $decreasing[0] = $arr[0];
    $tail2[0] = 0;
 
    for ($i = 1; $i < $n; $i++)
    {
        if ($arr[$i] < $decreasing[0])
        {
            $decreasing[0] = $arr[$i];
            $tail2[$i] = 0;
        }
        else if ($arr[$i] > $decreasing[$in - 1])
        {
            $decreasing[$in++] = $arr[$i];
            $tail2[$i] = $in - 1;
        }
        else
        {
            $decreasing[ceilIndex($decreasing, -1,
                    $in - 1, $arr[$i])] = $arr[$i];
            $tail2[$i] = ceilIndex($decreasing, -1,
                                $in - 1, $arr[$i]);
        }
    }
 
    revereseArr($arr, $n);
    revereseArr($tail2, $n);
 
    // Longest Bitonic Subsequence length is
    // maximum of tail1[i] + tail2[i] + 1:
    $ans = 0;
    for ($i = 0; $i < $n; $i++)
        if ($ans < ($tail1[$i] + $tail2[$i] + 1))
            $ans = ($tail1[$i] + $tail2[$i] + 1);
 
    return $ans;
}
 
// Driver code
$arr = array(0, 8, 4, 12, 2, 10, 6, 14,
             1, 9, 5, 13, 3, 11, 7, 15);
$n = sizeof($arr);
echo getLBSLengthLogn($arr, $n) . "\n";
 
// This code is contributed by ita_c
?>

Javascript

<script>
// Javascript program to find length of longest
// Bitonic subsequence in O (n Log n) time,
     
     
    function binarySearch(arr, x, start, end) {
        
    // Base Condition
    if (start > end) return false;
    
    // FInd the middle Index
    let mid=Math.floor((start + end)/2);
    
    // Compare mid with given key x
    if (arr[mid]===x) return true;
           
    // If element at mid is greater than x,
    // search In the left half of mid
    if(arr[mid] > x)
        return binarySearch(arr, x, start, mid-1);
    else
   
        // If element at mid is smaller than x,
        // search In the right half of mid
        return binarySearch(arr, x, mid+1, end);
    }
     
    // function to reverse an array
    function revereseArr(arr)
    {
        let i = 0;
        let j = arr.length - 1;
        while (i < j)
        {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;j--;
        }
    }
     
    // Returns length of longest Bitonic
    // subsequence in O(n Log n) time.
    function getLBSLengthLogn(arr)
    {
        let n = arr.length;
           
        // Base Case:
        if(n==0)
            return 0;
           
        /*Aux array storIng the Input array
        In same order to calculate LIS:*/
        let IncreasIng = new Array(n);
           
        //to store lengths of IS
        let tail1 = new Array(n);
           
        /*Aux array storIng the Input array
          In reverse order to calculate LIS:
          This will calculate Longest DecreasIng
          Subsequence which is required for
          Longest Bitonic Subsequence*/
        let decreasIng = new Array(n);
           
        // To store lengths of DS
        let tail2 = new Array(n);
           
        // InitializIng first Index same as
        // origInal array:
        IncreasIng[0] = arr[0];
           
        // Index In Initialized as 1 from where
        // the remaInIng computations will be done
        let In = 1;
           
        // tail1 stores Longest IncreasIng
        // subsequence length values till Index In
        tail1[0] = 0;
           
        // remaInIng computations to get the
        // LIS length for IncreasIng
        for(let i = 1; i < n; i++)
        {
            if(arr[i] < IncreasIng[0])
            {
                IncreasIng[0] = arr[i];
                tail1[i] = 0;
            }
            else if(arr[i] > IncreasIng[In - 1])
            {
                IncreasIng[In++] = arr[i];
                tail1[i] = In - 1;
            }
            else
            {
                let getIndex1 = binarySearch(IncreasIng,
                                                0, In, arr[i]);
                if(getIndex1 <= -1)
                    contInue;
                   
                IncreasIng[getIndex1] = arr[i];
                tail1[i] = getIndex1;
            }
        }
   
        // reInitializIng the Index to 1
        In = 1;
           
        // reversIng the array to get the Longest
        // DecreasIng Subsequence Length:
        revereseArr(arr);
        decreasIng[0] = arr[0];
        tail2[0] = 0;
           
        for(let i = 0; i < n; i++)
        {
            if(arr[i] < decreasIng[0])
            {
                decreasIng[0] = arr[i];
                tail2[i] = 0;
            }
            else if(arr[i] > decreasIng[In - 1])
            {
                decreasIng[In++] = arr[i];
                tail2[i] = In - 1;
            }
            else
            {
                let getIndex2 =  binarySearch(decreasIng,
                                                0, In , arr[i]);
                if(getIndex2 <= -1)
                    contInue;
               
                decreasIng[getIndex2] = arr[i];
                tail2[i] = getIndex2;
               
            }
        }
           
        revereseArr(arr);
        revereseArr(tail2);
        
        // Longest Bitonic Subsequence length is
        // maximum of tail1[i] + tail2[i] + 1:
        let ans = 0;
        for (let i = 0; i < n; i++)
        {
            if (ans < (tail1[i] + tail2[i] + 1))
                ans = (tail1[i] + tail2[i] + 1);
        }
        return ans;
    }
     
    // Driver code to test above methods
    let arr=[ 0, 8, 4, 12, 2, 10, 6, 14,
                      1, 9, 5, 13, 3, 11, 7, 15];
    document.write(getLBSLengthLogn(arr));
     
    // This code is contributed by avanitrachhadiya2155
</script>
Producción

7

Complejidad de Tiempo: O(nLogn) 
Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *