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