Dados dos arreglos arr[] y arr1[] de longitudes N y M respectivamente, la tarea es encontrar la subsecuencia creciente más larga del arreglo arr[] tal que no contenga el arreglo arr1[] como subarreglo .
Ejemplos:
Entrada: arr[] = {5, 3, 9, 3, 4, 7}, arr1[] = {3, 3, 7}
Salida: 4
Explicación: La subsecuencia creciente más larga requerida es {3, 3, 4, 7} .Entrada: arr[] = {1, 2, 3}, arr1[] = {1, 2, 3}
Salida: 2
Explicación: La subsecuencia creciente más larga requerida es {1, 2}.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de la subsecuencia más larga entre ellas, que no contiene arr1[] como subarreglo.
Complejidad de tiempo: O(M * 2 N ) donde N y M son las longitudes de las arrays dadas.
Espacio Auxiliar: O(M + N)
Enfoque eficiente: la idea es utilizar la array lps[] generada mediante el algoritmo KMP y la programación dinámica para encontrar la subsecuencia no decreciente más larga sin ningún subarreglo igual a la secuencia[] . Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[N][N][N] donde dp[i][j][K] almacena la longitud máxima de la subsecuencia no decreciente hasta el índice i donde j es el índice del elemento elegido previamente en la array arr[] y K denota que la secuencia encontrada actualmente contiene una secuencia de subarreglo[0, K] .
- Además, genere una array para almacenar la longitud del sufijo de prefijo más largo utilizando el algoritmo KMP .
- La longitud máxima se puede encontrar memorizando las siguientes transiciones dp:
dp(i, anterior, k) = max(1 + dp(i + 1, i, k2), dp(i + 1, anterior, k)) donde,
- i es el índice actual.
- prev es el elemento previamente elegido.
- k2 es el índice del subarreglo de prefijos incluido hasta ahora en la secuencia encontrada actualmente que se puede encontrar usando KMP Array para el sufijo de prefijo más largo.
Caso base:
- Si k es igual a la longitud de la secuencia dada, regresa ya que la subsecuencia actualmente encontrada contiene el arr1[].
- Si llego a N, regreso ya que no existen más elementos.
- Si el estado actual ya ha sido calculado, regrese.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Initialize dp and KMP array
int dp[6][6][6];
int KMPArray[2];
// Length of the given sequence[]
int m;
// Function to find the max-length
// subsequence that does not have
// subarray sequence[]
int findSubsequence(int a[], int sequence[], int i,
int prev, int k, int al, int sl)
{
// Stores the subsequence
// explored so far
if (k == m)
return INT_MIN;
// Base Case
if (i == al)
return 0;
// Using memoization to
// avoid re-computation
if (prev != -1 && dp[i][prev][k] != -1) {
return dp[i][prev][k];
}
int include = 0;
if (prev == -1 || a[i] >= a[prev]) {
int k2 = k;
// Using KMP array to find
// corresponding index in arr1[]
while (k2 > 0
&& a[i] != sequence[k2])
k2 = KMPArray[k2 - 1];
// Incrementing k2 as we are
// including this element in
// the subsequence
if (a[i] == sequence[k2])
k2++;
// Possible answer for
// current state
include = 1
+ findSubsequence(
a, sequence,
i + 1, i, k2, al, sl);
}
// Maximum answer for
// current state
int ans = max(
include, findSubsequence(
a, sequence,
i + 1, prev, k, al, sl));
// Memoizing the answer for
// the corresponding state
if (prev != -1) {
dp[i][prev][k] = ans;
}
// Return the answer for
// current state
return ans;
}
// Function that generate KMP Array
void fillKMPArray(int pattern[])
{
// Previous longest prefix suffix
int j = 0;
int i = 1;
// KMPArray[0] is a always 0
KMPArray[0] = 0;
// The loop calculates KMPArray[i]
// for i = 1 to M - 1
while (i < m) {
// If current character is
// same
if (pattern[i] == pattern[j]) {
j++;
// Update the KMP array
KMPArray[i] = j;
i++;
}
// Otherwise
else {
// Update the KMP array
if (j != 0)
j = KMPArray[j - 1];
else {
KMPArray[i] = j;
i++;
}
}
}
}
// Function to print the maximum
// possible length
void printAnswer(int a[], int sequence[], int al, int sl)
{
// Length of the given sequence
m = sl;
// Generate KMP array
fillKMPArray(sequence);
// Initialize the states to -1
memset(dp, -1, sizeof(dp));
// Get answer
int ans = findSubsequence(a, sequence, 0, -1, 0, al, sl);
// Print answer
cout << ((ans < 0) ? 0 : ans) << endl;
}
// Driver code
int main()
{
// Given array
int arr[] = { 5, 3, 9, 3, 4, 7 };
// Give arr1
int arr1[] = { 3, 4 };
// Function Call
printAnswer(arr, arr1, 6, 2);
return 0;
}
// This code is contributed by divyeshrabadiya07.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Initialize dp and KMP array
static int[][][] dp;
static int[] KMPArray;
// Length of the given sequence[]
static int m;
// Function to find the max-length
// subsequence that does not have
// subarray sequence[]
private static int findSubsequence(
int[] a, int[] sequence,
int i, int prev, int k)
{
// Stores the subsequence
// explored so far
if (k == m)
return Integer.MIN_VALUE;
// Base Case
if (i == a.length)
return 0;
// Using memoization to
// avoid re-computation
if (prev != -1
&& dp[i][prev][k] != -1) {
return dp[i][prev][k];
}
int include = 0;
if (prev == -1 || a[i] >= a[prev]) {
int k2 = k;
// Using KMP array to find
// corresponding index in arr1[]
while (k2 > 0
&& a[i] != sequence[k2])
k2 = KMPArray[k2 - 1];
// Incrementing k2 as we are
// including this element in
// the subsequence
if (a[i] == sequence[k2])
k2++;
// Possible answer for
// current state
include = 1
+ findSubsequence(
a, sequence,
i + 1, i, k2);
}
// Maximum answer for
// current state
int ans = Math.max(
include, findSubsequence(
a, sequence,
i + 1, prev, k));
// Memoizing the answer for
// the corresponding state
if (prev != -1) {
dp[i][prev][k] = ans;
}
// Return the answer for
// current state
return ans;
}
// Function that generate KMP Array
private static void
fillKMPArray(int[] pattern)
{
// Previous longest prefix suffix
int j = 0;
int i = 1;
// KMPArray[0] is a always 0
KMPArray[0] = 0;
// The loop calculates KMPArray[i]
// for i = 1 to M - 1
while (i < m) {
// If current character is
// same
if (pattern[i] == pattern[j]) {
j++;
// Update the KMP array
KMPArray[i] = j;
i++;
}
// Otherwise
else {
// Update the KMP array
if (j != 0)
j = KMPArray[j - 1];
else {
KMPArray[i] = j;
i++;
}
}
}
}
// Function to print the maximum
// possible length
static void printAnswer(
int a[], int sequence[])
{
// Length of the given sequence
m = sequence.length;
// Initialize kmp array
KMPArray = new int[m];
// Generate KMP array
fillKMPArray(sequence);
// Initialize dp
dp = new int[a.length][a.length][a.length];
// Initialize the states to -1
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a.length; j++)
Arrays.fill(dp[i][j], -1);
// Get answer
int ans = findSubsequence(
a, sequence, 0, -1, 0);
// Print answer
System.out.println((ans < 0) ? 0 : ans);
}
// Driver code
public static void
main(String[] args) throws Exception
{
// Given array
int[] arr = { 5, 3, 9, 3, 4, 7 };
// Give arr1
int[] arr1 = { 3, 4 };
// Function Call
printAnswer(arr, arr1);
}
}
Python3
# Python program for the above approach # Initialize dp and KMP array from pickle import GLOBAL import sys dp = [[[-1 for i in range(6)]for j in range(6)]for k in range(6)] KMPArray = [0 for i in range(2)] # Length of the given sequence[] m = 0 # Function to find the max-length # subsequence that does not have # subarray sequence[] def findSubsequence(a, sequence, i,prev, k, al, sl): global KMPArray global dp # Stores the subsequence # explored so far if (k == m): return -sys.maxsize -1 # Base Case if (i == al): return 0 # Using memoization to # avoid re-computation if (prev != -1 and dp[i][prev][k] != -1): return dp[i][prev][k] include = 0 if (prev == -1 or a[i] >= a[prev]): k2 = k # Using KMP array to find # corresponding index in arr1[] while (k2 > 0 and a[i] != sequence[k2]): k2 = KMPArray[k2 - 1] # Incrementing k2 as we are # including this element in # the subsequence if (a[i] == sequence[k2]): k2 += 1 # Possible answer for # current state include = 1 + findSubsequence( a, sequence, i + 1, i, k2, al, sl) # Maximum answer for # current state ans = max(include, findSubsequence( a, sequence, i + 1, prev, k, al, sl)) # Memoizing the answer for # the corresponding state if (prev != -1) : dp[i][prev][k] = ans # Return the answer for # current state return ans # Function that generate KMP Array def fillKMPArray(pattern): global m global KMPArray # Previous longest prefix suffix j = 0 i = 1 # KMPArray[0] is a always 0 KMPArray[0] = 0 # The loop calculates KMPArray[i] # for i = 1 to M - 1 while (i < m): # If current character is # same if (pattern[i] == pattern[j]): j += 1 # Update the KMP array KMPArray[i] = j i += 1 # Otherwise else: # Update the KMP array if (j != 0): j = KMPArray[j - 1] else: KMPArray[i] = j i += 1 # Function to print the maximum # possible length def printAnswer(a, sequence, al, sl): global m # Length of the given sequence m = sl # Generate KMP array fillKMPArray(sequence) # Get answer ans = findSubsequence(a, sequence, 0, -1, 0, al, sl) # Print answer if(ans < 0): print(0) else : print(ans) # Driver code # Given array arr = [ 5, 3, 9, 3, 4, 7 ] # Give arr1 arr1 = [ 3, 4 ] # Function Call printAnswer(arr, arr1, 6, 2) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Initialize dp and KMP array
static int[,,] dp;
static int[] KMPArray;
// Length of the given sequence[]
static int m;
// Function to find the max-length
// subsequence that does not have
// subarray sequence[]
private static int findSubsequence(int[] a,
int[] sequence,
int i, int prev,
int k)
{
// Stores the subsequence
// explored so far
if (k == m)
return int.MinValue;
// Base Case
if (i == a.Length)
return 0;
// Using memoization to
// avoid re-computation
if (prev != -1 && dp[i, prev, k] != -1)
{
return dp[i, prev, k];
}
int include = 0;
if (prev == -1 || a[i] >= a[prev])
{
int k2 = k;
// Using KMP array to find
// corresponding index in arr1[]
while (k2 > 0 && a[i] != sequence[k2])
k2 = KMPArray[k2 - 1];
// Incrementing k2 as we are
// including this element in
// the subsequence
if (a[i] == sequence[k2])
k2++;
// Possible answer for
// current state
include = 1 + findSubsequence(a, sequence,
i + 1, i, k2);
}
// Maximum answer for
// current state
int ans = Math.Max(include,
findSubsequence(a, sequence,
i + 1, prev, k));
// Memoizing the answer for
// the corresponding state
if (prev != -1)
{
dp[i, prev, k] = ans;
}
// Return the answer for
// current state
return ans;
}
// Function that generate KMP Array
private static void fillKMPArray(int[] pattern)
{
// Previous longest prefix suffix
int j = 0;
int i = 1;
// KMPArray[0] is a always 0
KMPArray[0] = 0;
// The loop calculates KMPArray[i]
// for i = 1 to M - 1
while (i < m)
{
// If current character is
// same
if (pattern[i] == pattern[j])
{
j++;
// Update the KMP array
KMPArray[i] = j;
i++;
}
// Otherwise
else
{
// Update the KMP array
if (j != 0)
j = KMPArray[j - 1];
else
{
KMPArray[i] = j;
i++;
}
}
}
}
// Function to print the maximum
// possible length
static void printAnswer(int[] a, int[] sequence)
{
// Length of the given sequence
m = sequence.Length;
// Initialize kmp array
KMPArray = new int[m];
// Generate KMP array
fillKMPArray(sequence);
// Initialize dp
dp = new int[a.Length, a.Length, a.Length];
// Initialize the states to -1
for(int i = 0; i < a.Length; i++)
for(int j = 0; j < a.Length; j++)
for(int k = 0; k < a.Length; k++)
dp[i, j, k] = -1;
// Get answer
int ans = findSubsequence(a, sequence, 0, -1, 0);
// Print answer
Console.WriteLine((ans < 0) ? 0 : ans);
}
// Driver code
public static void Main()
{
// Given array
int[] arr = { 5, 3, 9, 3, 4, 7 };
// Give arr1
int[] arr1 = { 3, 4 };
// Function Call
printAnswer(arr, arr1);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program to implement above approach
// Initialize dp and KMP array
let dp = new Array(6).fill(-1).map(()=>new Array(6).fill(-1).map(()=>new Array(6).fill(-1)));
let KMPArray = new Array(2);
// Length of the given sequence
let m;
// Function to find the max-length
// subsequence that does not have
// subarray sequence[]
function findSubsequence(a, sequence, i,prev, k, al, sl)
{
// Stores the subsequence
// explored so far
if (k == m)
return Number.MIN_VALUE;
// Base Case
if (i == al)
return 0;
// Using memoization to
// avoid re-computation
if (prev != -1 && dp[i][prev][k] != -1) {
return dp[i][prev][k];
}
let include = 0;
if (prev == -1 || a[i] >= a[prev]) {
let k2 = k;
// Using KMP array to find
// corresponding index in arr1[]
while (k2 > 0
&& a[i] != sequence[k2])
k2 = KMPArray[k2 - 1];
// Incrementing k2 as we are
// including this element in
// the subsequence
if (a[i] == sequence[k2])
k2++;
// Possible answer for
// current state
include = 1
+ findSubsequence(
a, sequence,
i + 1, i, k2, al, sl);
}
// Maximum answer for
// current state
let ans = Math.max(
include, findSubsequence(
a, sequence,
i + 1, prev, k, al, sl));
// Memoizing the answer for
// the corresponding state
if (prev != -1) {
dp[i][prev][k] = ans;
}
// Return the answer for
// current state
return ans;
}
// Function that generate KMP Array
function fillKMPArray(pattern)
{
// Previous longest prefix suffix
let j = 0;
let i = 1;
// KMPArray[0] is a always 0
KMPArray[0] = 0;
// The loop calculates KMPArray[i]
// for i = 1 to M - 1
while (i < m) {
// If current character is
// same
if (pattern[i] == pattern[j]) {
j++;
// Update the KMP array
KMPArray[i] = j;
i++;
}
// Otherwise
else {
// Update the KMP array
if (j != 0)
j = KMPArray[j - 1];
else {
KMPArray[i] = j;
i++;
}
}
}
}
// Function to print the maximum
// possible length
function printAnswer(a, sequence, al, sl)
{
// Length of the given sequence
m = sl;
// Generate KMP array
fillKMPArray(sequence);
// Get answer
let ans = findSubsequence(a, sequence, 0, -1, 0, al, sl);
// Print answer
console.log((ans < 0) ? 0 : ans);
}
// Driver code
// Given array
let arr = [ 5, 3, 9, 3, 4, 7 ];
// Give arr1
let arr1 = [ 3, 4 ];
// Function Call
printAnswer(arr, arr1, 6, 2);
// This code is contributed by shinjanpatra
</script>
Producción:
3
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N 3 )
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array