Maximize a contagem de subseqüências consecutivas decrescentes de uma array
Dado um array arr [] que consiste em N inteiros, a tarefa é encontrar a contagem máxima de subsequências decrescentes possíveis de um array que satisfaça as seguintes condições:
- Cada subsequência está em sua forma mais longa possível.
- A diferença entre os elementos adjacentes da subsequência é sempre 1 .
Exemplos:
Entrada: arr [] = {2, 1, 5, 4, 3}
Saída: 2
Explicação:
Possíveis subseqüências decrescentes são {5, 4, 3} e {2, 1}.
Entrada: arr [] = {4, 5, 2, 1, 4}
Saída: 3
Explicação:
Possíveis subseqüências decrescentes são {4}, {5, 4} e {2, 1}.
Abordagem:
A ideia é usar um HashMap para resolver o problema. Siga os passos abaixo:
- Mantenha um HashMap para armazenar a contagem de subsequências possíveis para um elemento da array e maxSubsequences para contar o número total de subsequências possíveis.
- Percorra a array e, para cada elemento arr [i] , verifique se existe alguma subsequência que possa ter arr [i] como o próximo elemento, pela contagem atribuída a arr [i] no HashMap .
- Se existir, faça o seguinte:
- Atribua arr [i] como o próximo elemento da subsequência.
- Diminua a contagem atribuída a arr [i] no HashMap , pois o número de subsequências possíveis com arr [i] como o próximo elemento diminuiu em 1 .
- Da mesma forma, aumente a contagem atribuída a arr [i] - 1 no HashMap , conforme o número de subsequências possíveis com arr [i] - 1 conforme o próximo elemento tenha aumentado em 1 .
- Caso contrário, aumente maxCount , pois uma nova subsequência é necessária e repita a etapa acima para modificar o HashMap .
- Depois de completar a travessia da array, imprima o valor de maxCount .
// C++ program to implememt
// 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 program to implememt
// 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# program to implememt
// 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# Python program to implememt
# 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.<script>
// Javascript program to implememt
// 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>Saída
3
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
