Dada una array arr[] que consta de N enteros, la tarea es encontrar el recuento máximo de subsecuencias decrecientes posibles de una array que satisfaga las siguientes condiciones:
- Cada subsecuencia está en su forma más larga posible.
- La diferencia entre elementos adyacentes de la subsecuencia es siempre 1 .
Ejemplos:
Entrada: arr[] = {2, 1, 5, 4, 3}
Salida: 2
Explicación:
Las posibles subsecuencias decrecientes son { 5, 4, 3 } y { 2, 1 }.
Entrada: arr[] = {4, 5, 2, 1, 4}
Salida: 3
Explicación:
Las posibles subsecuencias decrecientes son { 4 }, { 5, 4} y { 2, 1}.
Enfoque:
La idea es usar un HashMap para resolver el problema. Siga los pasos a continuación:
- Mantenga un HashMap para almacenar el recuento de subsecuencias posibles para un elemento de array y maxSubsequences para contar el número total de posibles subsecuencias.
- Recorra la array y, para cada elemento arr[i] , verifique si existe alguna subsecuencia que pueda tener arr[i] como el siguiente elemento, según el recuento asignado a arr[i] en el HashMap .
- Si existe, haga lo siguiente:
- Asigne arr[i] como el siguiente elemento de la subsecuencia.
- Reduzca el recuento asignado a arr[i] en el HashMap , ya que el número de posibles subsecuencias con arr[i] como el siguiente elemento ha disminuido en 1 .
- Del mismo modo, aumente el recuento asignado a arr[i] – 1 en HashMap , ya que el número de posibles subsecuencias con arr[i] – 1 a medida que el siguiente elemento ha aumentado en 1 .
- De lo contrario, aumente maxCount , ya que se requiere una nueva subsecuencia y repita el paso anterior para modificar HashMap .
- Después de completar el recorrido de la array, imprima el valor de maxCount .
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// number of required subsequences
int maxSubsequences(int arr[], int n)
{
// HashMap to store number of
// arrows available with
// height of arrow as key
unordered_map<int, int> m;
// Stores the maximum count
// of possible subsequences
int maxCount = 0;
// Stores the count of
// possible subsequences
int count;
for (int i = 0; i < n; i++) {
// Check if i-th element can be
// part of any of the previous
// subsequence
if (m.find(arr[i]) != m.end()) {
// Count of subsequences
// possible with arr[i] as
// the next element
count = m[arr[i]];
// If more than one such
// subsequence exists
if (count > 1) {
// Include arr[i] in a subsequence
m[arr[i]] = count - 1;
}
// Otherwise
else
m.erase(arr[i]);
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
m[arr[i] - 1] += 1;
}
else {
// Start a new subsequence
maxCount++;
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
m[arr[i] - 1] += 1;
}
}
// Return the answer
return maxCount;
}
// Driver Code
int main()
{
int n = 5;
int arr[] = { 4, 5, 2, 1, 4 };
cout << maxSubsequences(arr, n) << endl;
// This code is contributed by bolliranadheer
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to find the maximum number
// number of required subsequences
static int maxSubsequences(int arr[], int n)
{
// HashMap to store number of
// arrows available with
// height of arrow as key
HashMap<Integer, Integer> map
= new HashMap<>();
// Stores the maximum count
// of possible subsequences
int maxCount = 0;
// Stores the count of
// possible subsequences
int count;
for (int i = 0; i < n; i++)
{
// Check if i-th element can be
// part of any of the previous
// subsequence
if (map.containsKey(arr[i]))
{
// Count of subsequences
// possible with arr[i] as
// the next element
count = map.get(arr[i]);
// If more than one such
// subsequence exists
if (count > 1)
{
// Include arr[i] in a subsequence
map.put(arr[i], count - 1);
}
// Otherwise
else
map.remove(arr[i]);
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
map.put(arr[i] - 1,
map.getOrDefault(arr[i] - 1, 0) + 1);
}
else {
// Start a new subsequence
maxCount++;
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
map.put(arr[i] - 1,
map.getOrDefault(arr[i] - 1, 0) + 1);
}
}
// Return the answer
return maxCount;
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
int arr[] = { 4, 5, 2, 1, 4 };
System.out.println(maxSubsequences(arr, n));
}
}
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum number
// number of required subsequences
static int maxSubsequences(int []arr, int n)
{
// Dictionary to store number of
// arrows available with
// height of arrow as key
Dictionary<int,
int> map = new Dictionary<int,
int>();
// Stores the maximum count
// of possible subsequences
int maxCount = 0;
// Stores the count of
// possible subsequences
int count;
for(int i = 0; i < n; i++)
{
// Check if i-th element can be
// part of any of the previous
// subsequence
if (map.ContainsKey(arr[i]))
{
// Count of subsequences
// possible with arr[i] as
// the next element
count = map[arr[i]];
// If more than one such
// subsequence exists
if (count > 1)
{
// Include arr[i] in a subsequence
map.Add(arr[i], count - 1);
}
// Otherwise
else
map.Remove(arr[i]);
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
if (map.ContainsKey(arr[i] - 1))
map[arr[i] - 1]++;
else
map.Add(arr[i] - 1, 1);
}
else
{
// Start a new subsequence
maxCount++;
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
if (map.ContainsKey(arr[i] - 1))
map[arr[i] - 1]++;
else
map.Add(arr[i] - 1, 1);
}
}
// Return the answer
return maxCount;
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
int []arr = { 4, 5, 2, 1, 4 };
Console.WriteLine(maxSubsequences(arr, n));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python program to implement # the above approach from collections import defaultdict # Function to find the maximum number # number of required subsequences def maxSubsequences(arr, n)->int: # Dictionary to store number of # arrows available with # height of arrow as key m = defaultdict(int) # Stores the maximum count # of possible subsequences maxCount = 0 # Stores the count # of possible subsequences count = 0 for i in range(0, n): # Check if i-th element can be # part of any of the previous # subsequence if arr[i] in m.keys(): # Count of subsequences # possible with arr[i] as # the next element count = m[arr[i]] # If more than one such # subsequence exists if count > 1: # Include arr[i] in a subsequence m[arr[i]] = count - 1 # Otherwise else: m.pop(arr[i]) # Increase count of subsequence possible # with arr[i] - 1 as the next element if arr[i] - 1 > 0: m[arr[i] - 1] += 1 else: maxCount += 1 # Increase count of subsequence possible # with arr[i] - 1 as the next element if arr[i] - 1 > 0: m[arr[i] - 1] += 1 # Return the answer return maxCount # Driver Code if __name__ == '__main__': n = 5 arr = [4, 5, 2, 1, 4] print(maxSubsequences(arr, n)) # This code is contributed by Riddhi Jaiswal.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum number
// number of required subsequences
function maxSubsequences(arr, n)
{
// Dictionary to store number of
// arrows available with
// height of arrow as key
let map = new Map();
// Stores the maximum count
// of possible subsequences
let maxCount = 0;
// Stores the count of
// possible subsequences
let count;
for(let i = 0; i < n; i++)
{
// Check if i-th element can be
// part of any of the previous
// subsequence
if (map.has(arr[i]))
{
// Count of subsequences
// possible with arr[i] as
// the next element
count = map[arr[i]];
// If more than one such
// subsequence exists
if (count > 1)
{
// Include arr[i] in a subsequence
map.add(arr[i], count - 1);
}
// Otherwise
else
map.delete(arr[i]);
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
if (map.has(arr[i] - 1))
map[arr[i] - 1]++;
else
map.set(arr[i] - 1, 1);
}
else
{
// Start a new subsequence
maxCount++;
// Increase count of subsequence possible
// with arr[i] - 1 as the next element
if (arr[i] - 1 > 0)
if (map.has(arr[i] - 1))
map[arr[i] - 1]++;
else
map.set(arr[i] - 1, 1);
}
}
// Return the answer
return maxCount;
}
// Driver code
let n = 5;
let arr = [ 4, 5, 2, 1, 4 ];
document.write(maxSubsequences(arr, n));
</script>
Producción
3
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA