Número mínimo de eliminaciones para hacer una secuencia ordenada

Dada una array de n enteros. La tarea es eliminar o eliminar el número mínimo de elementos de la array para que cuando los elementos restantes se coloquen en el mismo orden de secuencia para formar una secuencia ordenada creciente .
Ejemplos: 
 

Input : {5, 6, 1, 7, 4}
Output : 2
Removing 1 and 4
leaves the remaining sequence order as
5 6 7 which is a sorted sequence.

Input : {30, 40, 2, 5, 1, 7, 45, 50, 8}
Output : 4

Una solución simple es eliminar todas las subsecuencias una por una y verificar si el conjunto restante de elementos está ordenado o no. La complejidad temporal de esta solución es exponencial.
Un enfoque eficiente utiliza el concepto de encontrar la longitud de la subsecuencia creciente más larga de una secuencia dada.
Algoritmo: 
 

-->arr be the given array.
-->n number of elements in arr.
-->len be the length of longest
   increasing subsequence in arr.
-->// minimum number of deletions
   min = n - len

C++

// C++ implementation to find
// minimum number of deletions
// to make a sorted sequence
#include <bits/stdc++.h>
using namespace std;
 
/* lis() returns the length
   of the longest increasing
   subsequence in arr[] of size n */
int lis( int arr[], int n )
{
    int result = 0;
    int lis[n];
 
    /* Initialize LIS values
    for all indexes */
    for (int i = 0; i < n; i++ )
        lis[i] = 1;
 
    /* Compute optimized LIS
       values in bottom up manner */
    for (int i = 1; i < n; i++ )
        for (int j = 0; j < i; j++ )
            if ( arr[i] > arr[j] &&
                 lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
 
    /* Pick resultimum
    of all LIS values */
    for (int i = 0; i < n; i++ )
        if (result < lis[i])
            result = lis[i];
 
    return result;
}
 
// function to calculate minimum
// number of deletions
int minimumNumberOfDeletions(int arr[],
                             int n)
{
    // Find longest increasing
    // subsequence
    int len = lis(arr, n);
 
    // After removing elements
    // other than the lis, we
    // get sorted sequence.
    return (n - len);
}
 
// Driver Code
int main()
{
    int arr[] = {30, 40, 2, 5, 1,
                   7, 45, 50, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum number of deletions = "
         << minimumNumberOfDeletions(arr, n);
    return 0;
}

Java

// Java implementation to find
// minimum number of deletions
// to make a sorted sequence
 
class GFG
{
    /* lis() returns the length
    of the longest increasing
    subsequence in arr[] of size n */
    static int lis( int arr[], int n )
    {
        int result = 0;
        int[] lis = new int[n];
     
        /* Initialize LIS values
        for all indexes */
        for (int i = 0; i < n; i++ )
            lis[i] = 1;
     
        /* Compute optimized LIS
           values in bottom up manner */
        for (int i = 1; i < n; i++ )
            for (int j = 0; j < i; j++ )
                if ( arr[i] > arr[j] &&
                    lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
     
        /* Pick resultimum of
        all LIS values */
        for (int i = 0; i < n; i++ )
            if (result < lis[i])
                result = lis[i];
     
        return result;
    }
     
    // function to calculate minimum
    // number of deletions
    static int minimumNumberOfDeletions(int arr[],
                                        int n)
    {
        // Find longest
        // increasing subsequence
        int len = lis(arr, n);
     
        // After removing elements
        // other than the lis, we get
        // sorted sequence.
        return (n - len);
    }
 
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = {30, 40, 2, 5, 1,
                       7, 45, 50, 8};
        int n = arr.length;
        System.out.println("Minimum number of" +
                               " deletions = " +
              minimumNumberOfDeletions(arr, n));
    }
}
 
/* This code is contributed by Harsh Agarwal */

Python3

# Python3 implementation to find
# minimum number of deletions to
# make a sorted sequence
 
# lis() returns the length
# of the longest increasing
# subsequence in arr[] of size n
def lis(arr, n):
 
    result = 0
    lis = [0 for i in range(n)]
 
    # Initialize LIS values
    # for all indexes
    for i in range(n):
        lis[i] = 1
 
    # Compute optimized LIS values
    # in bottom up manner
    for i in range(1, n):
        for j in range(i):
            if ( arr[i] > arr[j] and
                lis[i] < lis[j] + 1):
                lis[i] = lis[j] + 1
 
    # Pick resultimum
    # of all LIS values
    for i in range(n):
        if (result < lis[i]):
            result = lis[i]
 
    return result
 
# Function to calculate minimum
# number of deletions
def minimumNumberOfDeletions(arr, n):
 
    # Find longest increasing
    # subsequence
    len = lis(arr, n)
 
    # After removing elements
    # other than the lis, we
    # get sorted sequence.
    return (n - len)
 
 
# Driver Code
arr = [30, 40, 2, 5, 1,
          7, 45, 50, 8]
n = len(arr)
print("Minimum number of deletions = ",
      minimumNumberOfDeletions(arr, n))
         
# This code is contributed by Anant Agarwal.

C#

// C# implementation to find
// minimum number of deletions
// to make a sorted sequence
using System;
 
class GfG
{
     
    /* lis() returns the length of
    the longest increasing subsequence
    in arr[] of size n */
    static int lis( int []arr, int n )
    {
        int result = 0;
        int[] lis = new int[n];
     
        /* Initialize LIS values for
        all indexes */
        for (int i = 0; i < n; i++ )
            lis[i] = 1;
     
        /* Compute optimized LIS values
        in bottom up manner */
        for (int i = 1; i < n; i++ )
            for (int j = 0; j < i; j++ )
                if ( arr[i] > arr[j] &&
                     lis[i] < lis[j] + 1)
                  lis[i] = lis[j] + 1;
     
        /* Pick resultimum of all LIS
        values */
        for (int i = 0; i < n; i++ )
            if (result < lis[i])
                result = lis[i];
     
        return result;
    }
     
    // function to calculate minimum
    // number of deletions
    static int minimumNumberOfDeletions(
                        int []arr, int n)
    {
         
        // Find longest increasing
        // subsequence
        int len = lis(arr, n);
     
        // After removing elements other
        // than the lis, we get sorted
        // sequence.
        return (n - len);
    }
 
    // Driver Code
    public static void Main (String[] args)
    {
        int []arr = {30, 40, 2, 5, 1,
                       7, 45, 50, 8};
        int n = arr.Length;
        Console.Write("Minimum number of" +
                          " deletions = " +
         minimumNumberOfDeletions(arr, n));
    }
}
 
// This code is contributed by parashar.

PHP

<?php
// PHP implementation to find
// minimum number of deletions
// to make a sorted sequence
 
 
/* lis() returns the length of
   the longest increasing subsequence
   in arr[] of size n */
function lis( $arr, $n )
{
    $result = 0;
    $lis[$n] = 0;
 
    /* Initialize LIS values
       for all indexes */
    for ($i = 0; $i < $n; $i++ )
        $lis[$i] = 1;
 
    /* Compute optimized LIS
       values in bottom up manner */
    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;
 
    /* Pick resultimum of
    all LIS values */
    for ($i = 0; $i < $n; $i++ )
        if ($result < $lis[$i])
            $result = $lis[$i];
 
    return $result;
}
 
// function to calculate minimum
// number of deletions
function minimumNumberOfDeletions($arr, $n)
{
    // Find longest increasing
    // subsequence
    $len = lis($arr, $n);
 
    // After removing elements
    // other than the lis, we
    // get sorted sequence.
    return ($n - $len);
}
 
// Driver Code
$arr = array(30, 40, 2, 5, 1,
               7, 45, 50, 8);
$n = sizeof($arr) / sizeof($arr[0]);
echo "Minimum number of deletions = " ,
    minimumNumberOfDeletions($arr, $n);
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
// javascript implementation to find
// minimum number of deletions
// to make a sorted sequence
/* lis() returns the length
of the longest increasing
subsequence in arr[] of size n */
function lis(arr,n)
{
    let result = 0;
    let lis= new Array(n);
 
    /* Initialize LIS values
    for all indexes */
    for (let i = 0; i < n; i++ )
        lis[i] = 1;
 
    /* Compute optimized LIS
    values in bottom up manner */
    for (let i = 1; i < n; i++ )
        for (let j = 0; j < i; j++ )
            if ( arr[i] > arr[j] &&
                lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
 
    /* Pick resultimum
    of all LIS values */
    for (let i = 0; i < n; i++ )
        if (result < lis[i])
            result = lis[i];
 
    return result;
}
 
// function to calculate minimum
// number of deletions
function minimumNumberOfDeletions(arr,n)
{
 
    // Find longest increasing
    // subsequence
    let len = lis(arr,n);
 
    // After removing elements
    // other than the lis, we
    // get sorted sequence.
    return (n - len);
}
 
    let arr = [30, 40, 2, 5, 1,7, 45, 50, 8];
    let n = arr.length;
    document.write("Minimum number of deletions = "
    + minimumNumberOfDeletions(arr,n));
 
// This code is contributed by vaibhavrabadiya117.
</script>

Producción : 
 

Minimum number of deletions = 4 

Complejidad de tiempo: O(n 2 )
La complejidad de tiempo se puede reducir a O(nlogn) encontrando el tamaño de subsecuencia creciente más largo (N Log N) Ayush Jauhari
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

 

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 *