Dada una array arr[0..n-1] del elemento positivo. La tarea es imprimir los elementos restantes de arr[] después de la eliminación repetida de LIS (de tamaño superior a 1). Si hay varios LIS con la misma longitud, debemos elegir el LIS que termina primero.
Ejemplos:
Input : arr[] = {1, 2, 5, 3, 6, 4, 1}
Output : 1
Explanation :
{1, 2, 5, 3, 6, 4, 1} - {1, 2, 5, 6} = {3, 4, 1}
{3, 4, 1} - {3, 4} = {1}
Input : arr[] = {1, 2, 3, 1, 5, 2}
Output : -1
Explanation :
{1, 2, 3, 1, 5, 2} - {1, 2, 3, 5} = {1, 2}
{1, 2} - {1, 2} = {}
Input : arr[] = {5, 3, 2}
Output : 3
Encontramos repetidamente LIS y eliminamos sus elementos de una array.
// input vector array = arr[]
// max-sum LIS vector array = maxArray[]
while (arr.size())
{
// find LIS
lis = findLIS(arr, arr.size());
if (lis.size() < 2)
break;
// Remove lis elements from current array. Note
// that both lis[] and arr[] are sorted in
// increasing order.
for (i=0; i<arr.size() && lis.size()>0; i++)
{
if (arr[i] == lis[0])
{
// Remove lis element from arr[]
arr.erase(arr.begin()+i) ;
i--;
// erase the element from lis[]. This is
// needed to make sure that next element
// to be removed is first element of lis[]
lis.erase(lis.begin()) ;
}
}
}
// print remaining element of array
for (i=0; i<arr.size(); i++)
cout << arr[i] << " ";
if (i == 0)
cout << "-1";
C++
/* C++ program to find size of array after repeated
deletion of LIS */
#include <bits/stdc++.h>
using namespace std;
// Function to construct Maximum Sum LIS
vector<int> findLIS(vector<int> arr, int n)
{
// L[i] - The Maximum Sum Increasing
// Subsequence that ends with arr[i]
vector <vector<int> > L(n);
// L[0] is equal to arr[0]
L[0].push_back(arr[0]);
// start from index 1
for (int i = 1; i < n; i++)
{
// for every j less than i
for (int j = 0; j < i; j++)
{
/* L[i] = {MaxSum(L[j])} + arr[i]
where j < i and arr[j] < arr[i] */
if (arr[i] > arr[j] && (L[i].size() < L[j].size()))
L[i] = L[j];
}
// L[i] ends with arr[i]
L[i].push_back(arr[i]);
}
// set lis = LIS
// whose size is max among all
int maxSize = 1;
vector<int> lis;
for (vector<int> x : L)
{
// The > sign makes sure that the LIS
// ending first is chose.
if (x.size() > maxSize)
{
lis = x;
maxSize = x.size();
}
}
return lis;
}
// Function to minimize array
void minimize(int input[], int n)
{
vector<int> arr(input, input + n);
while (arr.size())
{
// Find LIS of current array
vector<int> lis = findLIS(arr, arr.size());
// If all elements are in decreasing order
if (lis.size() < 2)
break;
// Remove lis elements from current array. Note
// that both lis[] and arr[] are sorted in
// increasing order.
for (int i=0; i<arr.size() && lis.size()>0; i++)
{
// If first element of lis[] is found
if (arr[i] == lis[0])
{
// Remove lis element from arr[]
arr.erase(arr.begin()+i) ;
i--;
// Erase first element of lis[]
lis.erase(lis.begin()) ;
}
}
}
// print remaining element of array
int i;
for (i=0; i < arr.size(); i++)
cout << arr[i] << " ";
// print -1 for empty array
if (i == 0)
cout << "-1";
}
// Driver function
int main()
{
int input[] = { 3, 2, 6, 4, 5, 1 };
int n = sizeof(input) / sizeof(input[0]);
// minimize array after deleting LIS
minimize(input, n);
return 0;
}
Java
// Java program to find size
// of array after repeated
// deletion of LIS
import java.util.*;
class GFG{
// Function to conMaximum Sum LIS
static Vector<Integer> findLIS(Vector<Integer> arr,
int n)
{
// L[i] - The Maximum Sum Increasing
// Subsequence that ends with arr[i]
Vector<Integer> []L = new Vector[n];
for (int i = 0; i < L.length; i++)
L[i] = new Vector<Integer>();
// L[0] is equal to arr[0]
L[0].add(arr.elementAt(0));
// Start from index 1
for (int i = 1; i < n; i++)
{
// For every j less than i
for (int j = 0; j < i; j++)
{
// L[i] = {MaxSum(L[j])} + arr[i]
// where j < i and arr[j] < arr[i]
if (arr.elementAt(i) > arr.elementAt(j) &&
(L[i].size() < L[j].size()))
L[i] = L[j];
}
// L[i] ends with arr[i]
L[i].add(arr.elementAt(i));
}
// Set lis = LIS
// whose size is max among all
int maxSize = 1;
Vector<Integer> lis = new Vector<>();
for (Vector<Integer> x : L)
{
// The > sign makes sure that the LIS
// ending first is chose.
if (x.size() > maxSize)
{
lis = x;
maxSize = x.size();
}
}
return lis;
}
// Function to minimize array
static void minimize(int input[],
int n)
{
Vector<Integer> arr = new Vector<>();
for(int i = 0; i < n; i++)
arr.add(input[i]);
while (arr.size() != 0)
{
// Find LIS of current array
Vector<Integer> lis = findLIS(arr,
arr.size());
// If all elements are
// in decreasing order
if (lis.size() < 2)
break;
// Remove lis elements from
// current array. Note that both
// lis[] and arr[] are sorted in
// increasing order.
for (int i = 0; i < arr.size() &&
lis.size() > 0; i++)
{
// If first element of lis[] is found
if (arr.elementAt(i) == lis.elementAt(0))
{
// Remove lis element from arr[]
arr.removeAll(lis);
i--;
// Erase first element of lis[]
lis.remove(0);
}
}
}
// print remaining element of array
int i;
for (i = 1; i < arr.size(); i++)
System.out.print(arr.elementAt(i) + " ");
// print -1 for empty array
if (i == 0)
System.out.print("-1");
}
// Driver function
public static void main(String[] args)
{
int input[] = {3, 2, 6, 4, 5, 1};
int n = input.length;
// minimize array after deleting LIS
minimize(input, n);
}
}
// This code is contributed by gauravrajput1
Python3
''' Python program to find size of array after repeated
deletion of LIS '''
# Function to construct Maximum Sum LIS
from typing import List
def findLIS(arr: List[int], n: int) -> List[int]:
# L[i] - The Maximum Sum Increasing
# Subsequence that ends with arr[i]
L = [0] * n
for i in range(n):
L[i] = []
# L[0] is equal to arr[0]
L[0].append(arr[0])
# start from index 1
for i in range(1, n):
# for every j less than i
for j in range(i):
''' L[i] = MaxSum(L[j]) + arr[i]
where j < i and arr[j] < arr[i] '''
if (arr[i] > arr[j] and
(len(L[i]) < len(L[j]))):
L[i] = L[j].copy()
# L[i] ends with arr[i]
L[i].append(arr[i])
# set lis = LIS
# whose size is max among all
maxSize = 1
lis: List[int] = []
for x in L:
# The > sign makes sure that the LIS
# ending first is chose.
if (len(x) > maxSize):
lis = x.copy()
maxSize = len(x)
return lis
# Function to minimize array
def minimize(input: List[int], n: int) -> None:
arr = input.copy()
while len(arr):
# Find LIS of current array
lis = findLIS(arr, len(arr))
# If all elements are in decreasing order
if (len(lis) < 2):
break
# Remove lis elements from current array. Note
# that both lis[] and arr[] are sorted in
# increasing order.
i = 0
while i < len(arr) and len(lis) > 0:
# If first element of lis[] is found
if (arr[i] == lis[0]):
# Remove lis element from arr[]
arr.remove(arr[i])
i -= 1
# Erase first element of lis[]
lis.remove(lis[0])
i += 1
# print remaining element of array
i = 0
while i < len(arr):
print(arr[i], end=" ")
i += 1
# print -1 for empty array
if (i == 0):
print("-1")
# Driver function
if __name__ == "__main__":
input = [3, 2, 6, 4, 5, 1]
n = len(input)
# minimize array after deleting LIS
minimize(input, n)
# This code is contributed by sanjeev2552
Producción:
1
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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 review-team@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