Size of array after repeated deletion of LIS
Given an array arr[0..n-1] of the positive element. The task is to print the remaining elements of arr[] after repeated deletion of LIS (of size greater than 1). If there are multiple LIS with the same length, we need to choose the LIS that ends first.
Examples:
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
We repeatedly find LIS and remove its elements from an 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 |
C#
using System; using System.Collections.Generic; class GFG { // Function to construct Maximum Sum LIS static List< int > findLIS(List< int > arr, int n) { // L[i] - The Maximum Sum Increasing // Subsequence that ends with arr[i] List<List< int > > L = new List<List< int > >(); for ( int i = 0; i < n; i++) { L.Add( new List< int >()); } // L[0] is equal to arr[0] L[0].Add(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].Count < L[j].Count)) L[i] = new List< int >(L[j]); } // L[i] ends with arr[i] L[i].Add(arr[i]); } // set lis = LIS // whose size is max among all int maxSize = 1; List< int > lis = new List< int >(); foreach (List< int > x in L) { // The > sign makes sure that the LIS // ending first is chose. if (x.Count > maxSize) { lis = x; maxSize = x.Count; } } return lis; } // Function to minimize array static void minimize( int [] input, int n) { List< int > arr = new List< int >(input); while (arr.Count > 0) { // Find LIS of current array List< int > lis = findLIS(arr, arr.Count); // If all elements are in decreasing order if (lis.Count < 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.Count; i++) { if (lis.Contains(arr[i])) { arr.RemoveAt(i); i--; } } } int j = 0; // print remaining element of array for (j = 0; j < arr.Count; j++) Console.Write(arr[j] + " " ); // print -1 for empty array if (j == 0) Console.Write( "-1" ); } // Driver function static void Main() { 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 agrawalpoojaa976. |
Javascript
// JavaScript program to find size of array after repeated // deletion of LIS // Function to construct Maximum Sum LIS function findLIS(arr) { let n = arr.length; // L[i] - The Maximum Sum Increasing // Subsequence that ends with arr[i] let L = Array(n).fill().map(() => []); // L[0] is equal to arr[0] L[0].push(arr[0]); // start from index 1 for (let i = 1; i < n; i++) { // for every j less than i for (let 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].length < L[j].length)) L[i] = L[j]; } // L[i] ends with arr[i] L[i].push(arr[i]); } // set lis = LIS // whose size is max among all let maxSize = 1; let lis = []; for (let x of L) { // The > sign makes sure that the LIS // ending first is chose. if (x.length > maxSize) { lis = x; maxSize = x.length; } } return lis; } // Function to minimize array function minimize(input) { let arr = input.slice(); while (arr.length) { // Find LIS of current array let lis = findLIS(arr); // If all elements are in decreasing order if (lis.length < 2) break ; // Remove lis elements from current array. Note // that both lis[] and arr[] are sorted in // increasing order. for (let i = 0; i < arr.length && lis.length > 0; i++) { // If first element of lis[] is found if (arr[i] === lis[0]) { // Remove lis element from arr[] arr.splice(i, 1); i--; // Erase first element of lis[] lis.shift(); } } } // print remaining element of array if (arr.length) { console.log(arr[1]); } else { console.log(-1); } } // Driver function let input = [3, 2, 6, 4, 5, 1]; // minimize array after deleting LIS minimize(input); // This code is contributed by lokeshpotta20. |
Output:
1
Time Complexity:O(n^2)
Space Complexity:O(n)