Dada una array arr[] de N enteros, la tarea es encontrar la longitud de la subsecuencia creciente más larga de modo que forme una subarreferencia cuando se ordena la array original.
Ejemplos:
Entrada: arr[] = { 2, 6, 4, 8, 2, 9 }
Salida: 3
Explicación:
array ordenada: {2, 2, 4, 6, 8, 9}
Todas las posibles secuencias no decrecientes de la array original son
{2}, {6}, {4}, {8}, {2}, {9}, {2, 2}, {6, 8}, {8, 9}, {6, 8, 9} .
De todas las subsecuencias anteriores, {6, 8, 9} es la subsecuencia más larga que es un subarreglo en la representación ordenada del arreglo.Entrada: arr[] = { 5, 5, 6, 6, 5, 5, 5, 6, 5, 5 }
Salida: 7
Explicación:
array ordenada: {5, 5, 5, 5, 5, 5, 5, 6, 6, 6}
{5, 5, 5, 5, 5, 5, 5} es la subsecuencia más larga que forma un subarreglo en la forma ordenada del arreglo.
Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de la array y luego verificar cuál de ellas forma la subarreglo más larga cuando se ordena la array original.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el enfoque de programación dinámica para resolver este problema. A continuación se muestran los pasos:
- Almacene la frecuencia de cada elemento en la array dada en un Map .
- Almacene la array original en una array temporal y ordene la array dada.
- Inicialice una array 2D de tamaño N * 3 donde:
- dp[N][i] almacenará el conteo de números X hasta la posición i .
- dp[x][1] almacenará el recuento del número X + el recuento de números (X – 1) hasta la posición i .
- dp[x][2] almacenará la longitud real de la secuencia hasta la posición i .
- Itere sobre la array original y para cada índice i en la array original, incluya el elemento en la posición actual i solo cuando todos los elementos (X – 1) ya estén incluidos en la subsecuencia y actualice los valores en dp[][] y actualice el tamaño máximo de la subsecuencia después de este estado.
- Imprima el tamaño máximo de la subsecuencia después de completar los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the
// longest increasing sorted sequence
int LongestSequence(int a[], int n)
{
// Stores the count of all elements
map<int, int> m;
int ar[n + 1], i, j;
// Store the original array
for (i = 1; i <= n; i++) {
ar[i] = a[i - 1];
}
// Sort the array
sort(a, a + n);
int c = 1;
m[a[0]] = c;
for (i = 1; i <= n; i++) {
// If adjacent element
// are not same
if (a[i] != a[i - 1]) {
// Increment count
c++;
m[a[i]] = c;
}
}
// Store frequency of each element
map<int, int> cnt;
// Initialize a DP array
int dp[n + 1][3] = { 0 };
cnt[0] = 0;
// Iterate over the array ar[]
for (i = 1; i <= n; i++) {
ar[i] = m[ar[i]];
cnt[ar[i]]++;
}
// Length of the longest
// increasing sorted sequence
int ans = 0, x;
// Iterate over the array
for (i = 1; i <= n; i++) {
// Current element
x = ar[i];
// If the element has been
// encountered the first time
if (dp[x][0] == 0) {
// If all the x - 1 previous
// elements have already appeared
if (dp[x - 1][0] == cnt[x - 1]) {
dp[x][1] = dp[x - 1][1];
dp[x][2] = dp[x - 1][1];
}
// Otherwise
else {
dp[x][1] = dp[x - 1][0];
}
}
dp[x][2] = max(dp[x - 1][0],
dp[x][2]);
if (dp[x - 1][0] == cnt[x - 1]) {
// If all x-1 elements have
// already been encountered
dp[x][2] = max(dp[x][2],
dp[x - 1][1]);
}
for (j = 0; j < 3; j++) {
// Increment the count of
// the current element
dp[x][j]++;
// Update maximum
// subsequence size
ans = max(ans, dp[x][j]);
}
}
// Return the maximum
// subsequence size
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 6, 4, 8, 2, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << LongestSequence(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the length of the
// longest increasing sorted sequence
static int LongestSequence(int a[], int n)
{
// Stores the count of all elements
HashMap<Integer, Integer> m = new HashMap<>();
int ar[] = new int[n + 1];
int i = 0;
int j = 0;
// Store the original array
for(i = 1; i <= n; i++)
{
ar[i] = a[i - 1];
}
// Sort the array
Arrays.sort(a);
int c = 1;
m.put(a[0], c);
for(i = 1; i < n; i++)
{
// If adjacent element
// are not same
if (a[i] != a[i - 1])
{
// Increment count
c++;
m.put(a[i], c);
}
}
// Store frequency of each element
HashMap<Integer, Integer> cnt = new HashMap<>();
// Initialize a DP array
int dp[][] = new int[n + 1][3];
cnt.put(0, 0);
// Iterate over the array ar[]
for(i = 1; i <= n; i++)
{
ar[i] = m.get(ar[i]);
if (cnt.containsKey(ar[i]))
cnt.put(ar[i], cnt.get(ar[i]) + 1);
else
cnt.put(ar[i], 1);
}
// Length of the longest
// increasing sorted sequence
int ans = 0, x;
// Iterate over the array
for(i = 1; i <= n; i++)
{
// Current element
x = ar[i];
// If the element has been
// encountered the first time
if (dp[x][0] == 0)
{
// If all the x - 1 previous
// elements have already appeared
if (dp[x - 1][0] == cnt.get(x - 1))
{
dp[x][1] = dp[x - 1][1];
dp[x][2] = dp[x - 1][1];
}
// Otherwise
else
{
dp[x][1] = dp[x - 1][0];
}
}
dp[x][2] = Math.max(dp[x - 1][0],
dp[x][2]);
if (dp[x - 1][0] == cnt.get(x - 1))
{
// If all x-1 elements have
// already been encountered
dp[x][2] = Math.max(dp[x][2],
dp[x - 1][1]);
}
for(j = 0; j < 3; j++)
{
// Increment the count of
// the current element
dp[x][j]++;
// Update maximum
// subsequence size
ans = Math.max(ans, dp[x][j]);
}
}
// Return the maximum
// subsequence size
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 6, 4, 8, 2, 9 };
int n = arr.length;
System.out.println(LongestSequence(arr, n));
}
}
// This code is contributed by bikram2001jha
Python3
# Python 3 program to implement
# the above approach
# Function to find the length of the
# longest increasing sorted sequence
def LongestSequence(a, n):
# Stores the count of all elements
m = {i : 0 for i in range(100)}
ar = [0 for i in range(n + 1)]
# Store the original array
for i in range(1, n + 1):
ar[i] = a[i - 1]
# Sort the array
a.sort(reverse = False)
c = 1
m[a[0]] = c
for i in range(1, n):
# If adjacent element
# are not same
if (a[i] != a[i - 1]):
# Increment count
c += 1
m[a[i]] = c
# Store frequency of each element
cnt = {i : 0 for i in range(100)}
# Initialize a DP array
dp = [[0 for i in range(3)]
for j in range(n + 1)]
cnt[0] = 0
# Iterate over the array ar[]
for i in range(1, n + 1):
ar[i] = m[ar[i]]
cnt[ar[i]] += 1
# Length of the longest
# increasing sorted sequence
ans = 0
# Iterate over the array
for i in range(1, n + 1):
# Current element
x = ar[i]
# If the element has been
# encountered the first time
if (dp[x][0] == 0):
# If all the x - 1 previous
# elements have already appeared
if (dp[x - 1][0] == cnt[x - 1]):
dp[x][1] = dp[x - 1][1]
dp[x][2] = dp[x - 1][1]
# Otherwise
else:
dp[x][1] = dp[x - 1][0]
dp[x][2] = max(dp[x - 1][0], dp[x][2])
if (dp[x - 1][0] == cnt[x - 1]):
# If all x-1 elements have
# already been encountered
dp[x][2] = max(dp[x][2], dp[x - 1][1])
for j in range(3):
# Increment the count of
# the current element
dp[x][j] += 1
# Update maximum
# subsequence size
ans = max(ans, dp[x][j])
# Return the maximum
# subsequence size
return ans
# Driver Code
if __name__ == '__main__':
arr = [ 2, 6, 4, 8, 2, 9 ]
N = len(arr)
# Function call
print(LongestSequence(arr, N))
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to find the length of the
// longest increasing sorted sequence
static int LongestSequence(int []a, int n)
{
// Stores the count of all elements
Dictionary<int,
int> m = new Dictionary<int,
int>();
int []ar = new int[n + 1];
int i = 0;
int j = 0;
// Store the original array
for(i = 1; i <= n; i++)
{
ar[i] = a[i - 1];
}
// Sort the array
Array.Sort(a);
int c = 1;
m[a[0]]= c;
for(i = 1; i < n; i++)
{
// If adjacent element
// are not same
if (a[i] != a[i - 1])
{
// Increment count
c++;
m[a[i]]= c;
}
}
// Store frequency of each element
Dictionary<int,
int>cnt = new Dictionary<int,
int>();
// Initialize a DP array
int [,]dp = new int[n + 1, 3];
cnt[0] = 0;
// Iterate over the array ar[]
for(i = 1; i <= n; i++)
{
ar[i] = m[ar[i]];
if (cnt.ContainsKey(ar[i]))
cnt[ar[i]]= cnt[ar[i]] + 1;
else
cnt[ar[i]]= 1;
}
// Length of the longest
// increasing sorted sequence
int ans = 0, x;
// Iterate over the array
for(i = 1; i <= n; i++)
{
// Current element
x = ar[i];
// If the element has been
// encountered the first time
if (dp[x, 0] == 0)
{
// If all the x - 1 previous
// elements have already appeared
if (dp[x - 1, 0] == cnt[x - 1])
{
dp[x, 1] = dp[x - 1, 1];
dp[x, 2] = dp[x - 1, 1];
}
// Otherwise
else
{
dp[x, 1] = dp[x - 1, 0];
}
}
dp[x, 2] = Math.Max(dp[x - 1, 0],
dp[x, 2]);
if (dp[x - 1, 0] == cnt[x - 1])
{
// If all x-1 elements have
// already been encountered
dp[x, 2] = Math.Max(dp[x, 2],
dp[x - 1, 1]);
}
for(j = 0; j < 3; j++)
{
// Increment the count of
// the current element
dp[x, j]++;
// Update maximum
// subsequence size
ans = Math.Max(ans, dp[x, j]);
}
}
// Return the maximum
// subsequence size
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 2, 6, 4, 8, 2, 9 };
int n = arr.Length;
Console.WriteLine(LongestSequence(arr, n));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the length of the
// longest increasing sorted sequence
function LongestSequence(a, n)
{
// Stores the count of all elements
var m = new Map();
var ar = Array(n+1).fill(0), i, j;
// Store the original array
for (i = 1; i <= n; i++) {
ar[i] = a[i - 1];
}
// Sort the array
a.sort((a,b)=>a-b);
var c = 1;
m.set(a[0], c);
for (i = 1; i <= n; i++) {
// If adjacent element
// are not same
if (a[i] != a[i - 1]) {
// Increment count
c++;
m.set(a[i], c);
}
}
// Store frequency of each element
var cnt = new Map();
// Initialize a DP array
var dp = Array.from(Array(n+1), ()=>Array(3).fill(0));
cnt.set(0, 0);
// Iterate over the array ar[]
for (i = 1; i <= n; i++) {
ar[i] = m.get(ar[i]);
if(cnt.has(ar[i]))
cnt.set(ar[i], cnt.get(ar[i])+1)
else
cnt.set(ar[i], 1)
}
// Length of the longest
// increasing sorted sequence
var ans = 0, x;
// Iterate over the array
for (i = 1; i <= n; i++) {
// Current element
x = ar[i];
// If the element has been
// encountered the first time
if (dp[x][0] == 0) {
// If all the x - 1 previous
// elements have already appeared
if (dp[x - 1][0] == cnt.get(x - 1)) {
dp[x][1] = dp[x - 1][1];
dp[x][2] = dp[x - 1][1];
}
// Otherwise
else {
dp[x][1] = dp[x - 1][0];
}
}
dp[x][2] = Math.max(dp[x - 1][0],
dp[x][2]);
if (dp[x - 1][0] == cnt[x - 1]) {
// If all x-1 elements have
// already been encountered
dp[x][2] = Math.max(dp[x][2],
dp[x - 1][1]);
}
for (j = 0; j < 3; j++) {
// Increment the count of
// the current element
dp[x][j]++;
// Update maximum
// subsequence size
ans = Math.max(ans, dp[x][j]);
}
}
// Return the maximum
// subsequence size
return ans;
}
// Driver Code
var arr = [2, 6, 4, 8, 2, 9];
var N = arr.length;
// Function Call
document.write( LongestSequence(arr, N));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA