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)
This article is contributed by Shivam Pradhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
