Dada una array arr[] que consta de N enteros y una array Consultas[][] con cada consulta de la forma {x, y} . Para cada consulta, la tarea es reemplazar el elemento en el índice x ( indexación basada en 1 ) por y y encontrar la longitud de la subsecuencia más larga que no tenga elementos adyacentes similares.
Ejemplos:
Entrada: arr[] = {1, 1, 2, 5, 2}, Q = 2, Queries[][] = {{1, 3}, {4, 2}}
Salida: 5 3
Explicación:
Inicialmente la array es {1, 1, 2, 5, 2}.
Consulta 1: modificando el valor en el índice 1 a 3, la array se modifica a {3, 1, 2, 5, 2}.
Por lo tanto, la subsecuencia más larga que no tiene elementos adyacentes similares es {3, 1, 2, 5, 2}, que tiene una longitud de 5.
Por lo tanto, escriba 5 como respuesta.
Consulta 2: modificando el valor en el índice 4 a 2, la array se modifica a {3, 1, 2, 2, 2}.
Ahora, por lo tanto, la subsecuencia más larga que no tiene elementos adyacentes similares es {3, 1, 2}, que tiene una longitud de 3.
Por lo tanto, imprime 2 como respuesta.Entrada: arr[] = {1, 1, 2, 5, 2}, Q = 1, Queries[][] = {{2, 2}}
Salida: 4
Explicación:
Inicialmente, la array es {1, 1, 2 , 5, 2}.
Consulta 1: modificando el valor en el índice 2 a 2, la array se modificó a {1, 2, 2, 5, 2}.
Por lo tanto, la subsecuencia más larga que no tiene elementos adyacentes similares es {1, 2, 5, 2}, que tiene una longitud de 4.
Por lo tanto, imprime el valor como 4.
Enfoque ingenuo: siga los pasos a continuación para resolver el problema utilizando el enfoque más simple posible:
- Agregue el elemento a la subsecuencia solo si no es igual al elemento anterior de la subsecuencia.
- Para cada consulta {x, y} , reemplace el elemento en el índice x con y .
- Realice un seguimiento de la subsecuencia más larga encontrada en cualquier punto mediante un conteo variable .
- Recorra la array e incremente la variable de conteo en 1 siempre que el elemento actual de la secuencia no sea igual al elemento anterior de la secuencia.
- Después de iterar la secuencia una vez, count contiene la longitud de la subsecuencia requerida más larga.
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;
// Function to find the length of the
// longest subsequence such that no
// two adjacent elements are equal
void longestSubsequence(int N, int Q,
int arr[],
int Queries[][2])
{
for (int i = 0; i < Q; i++) {
// Replace element at
// index x with y
int x = Queries[i][0];
int y = Queries[i][1];
// Since x is 1-indexed,
// decrement x by 1
arr[x - 1] = y;
// Keep track of number of
// elements in subsequence
int count = 1;
for (int j = 1; j < N; j++) {
// If previous element is not
// same as current element
if (arr[j] != arr[j - 1]) {
count += 1;
}
}
// Print the desired count
cout << count << ' ';
}
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 5, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 2;
int Queries[Q][2] = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the length of the
// longest subsequence such that no
// two adjacent elements are equal
static void longestSubsequence(int N, int Q,
int arr[],
int Queries[][])
{
for (int i = 0; i < Q; i++)
{
// Replace element at
// index x with y
int x = Queries[i][0];
int y = Queries[i][1];
// Since x is 1-indexed,
// decrement x by 1
arr[x - 1] = y;
// Keep track of number of
// elements in subsequence
int count = 1;
for (int j = 1; j < N; j++)
{
// If previous element is not
// same as current element
if (arr[j] != arr[j - 1])
{
count += 1;
}
}
// Print the desired count
System.out.print(count +" ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 5, 2 };
int N = arr.length;
int Q = 2;
int Queries[][] = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to find the length of the # longest subsequence such that no # two adjacent elements are equal def longestSubsequence(N, Q, arr, Queries): for i in range(Q): # Replace element at # index x with y x = Queries[i][0] y = Queries[i][1] # Since x is 1-indexed, # decrement x by 1 arr[x - 1] = y # Keep track of number of # elements in subsequence count = 1 for j in range(1, N): # If previous element is not # same as current element if (arr[j] != arr[j - 1]): count += 1 # Print the desired count print(count, end = ' ') # Driver Code if __name__ == "__main__": arr = [ 1, 1, 2, 5, 2 ] N = len(arr) Q = 2 Queries = [ [ 1, 3 ], [ 4, 2 ] ] # Function Call longestSubsequence(N, Q, arr, Queries) # This code is contributed by chitranayal
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the length of the
// longest subsequence such that no
// two adjacent elements are equal
static void longestSubsequence(int N, int Q,
int []arr,
int [,]Queries)
{
for(int i = 0; i < Q; i++)
{
// Replace element at
// index x with y
int x = Queries[i, 0];
int y = Queries[i, 1];
// Since x is 1-indexed,
// decrement x by 1
arr[x - 1] = y;
// Keep track of number of
// elements in subsequence
int count = 1;
for(int j = 1; j < N; j++)
{
// If previous element is not
// same as current element
if (arr[j] != arr[j - 1])
{
count += 1;
}
}
// Print the desired count
Console.Write(count +" ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 1, 2, 5, 2 };
int N = arr.Length;
int Q = 2;
int[,]Queries = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
}
}
// This code is contributed by jana_sayantan
Javascript
<script>
// JavaScript implementation of the above approach
// Function to find the length of the
// longest subsequence such that no
// two adjacent elements are equal
function longestSubsequence(N, Q,
arr, Queries)
{
for (let i = 0; i < Q; i++)
{
// Replace element at
// index x with y
let x = Queries[i][0];
let y = Queries[i][1];
// Since x is 1-indexed,
// decrement x by 1
arr[x - 1] = y;
// Keep track of number of
// elements in subsequence
let count = 1;
for (let j = 1; j < N; j++)
{
// If previous element is not
// same as current element
if (arr[j] != arr[j - 1])
{
count += 1;
}
}
// Print the desired count
document.write(count +" ");
}
}
// Driver code
let arr = [ 1, 1, 2, 5, 2 ];
let N = arr.length;
let Q = 2;
let Queries = [[ 1, 3 ], [ 4, 2 ]];
// Function Call
longestSubsequence(N, Q, arr, Queries);
// This code is contributed by code_hunt.
</script>
Producción:
5 3
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, se encuentra una observación de que la presencia de un elemento en la subsecuencia requerida solo depende de su elemento anterior, como se muestra a continuación:
- Reemplazar el elemento en el índice x solo afectará la contribución de los elementos en los índices x y x + 1 , en la respuesta final.
- Por lo tanto, restar las contribuciones de estos 2 índices del conteo de variables y volver a calcular las contribuciones de estos 2 índices dará la respuesta requerida en tiempo constante.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count , para almacenar el recuento de subsecuencias.
- Recorra la array dada y cuente los elementos que son diferentes del elemento anterior de la array y guárdelo en una variable count .
- Ahora recorra cada consulta {x, y} y realice lo siguiente:
- Si el elemento en el índice (x – 1) es diferente del elemento en el índice x , entonces disminuya el conteo en 1 .
- Si el elemento en el índice (x – 1) es diferente del elemento y , entonces incremente el conteo en 1 .
- De manera similar, si el elemento en el índice (x + 1) es diferente del elemento en el índice x , entonces disminuya el conteo en 1 .
- Si el elemento en el índice (x + 1) es diferente del elemento y , entonces incremente el conteo en 1 .
- Imprime el valor de count después de cada consulta como resultado.
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;
void longestSubsequence(int N, int Q,
int arr[],
int Queries[][2])
{
int count = 1;
// Traverse the array arr[]
for (int i = 1; i < N; i++) {
// If previous element is not
// same as current element
if (arr[i] != arr[i - 1]) {
count += 1;
}
}
// Traverse the queries
for (int i = 0; i < Q; i++) {
// Replace element at
// index x with y
int x = Queries[i][0];
int y = Queries[i][1];
// Recalculate for index x
if (x > 1) {
// Subtract contribution
// of element at index x
if (arr[x - 1] != arr[x - 2]) {
count -= 1;
}
// Add contribution of y
if (arr[x - 2] != y) {
count += 1;
}
}
// Recalculate for index x + 1
if (x < N) {
// Subtract contribution of
// element at index x + 1
if (arr[x] != arr[x - 1]) {
count -= 1;
}
// Adds contribution of y
if (y != arr[x]) {
count += 1;
}
}
cout << count << ' ';
// Replace the element
arr[x - 1] = y;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 2, 5, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 2;
int Queries[Q][2] = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static void longestSubsequence(int N, int Q,
int arr[],
int Queries[][])
{
int count = 1;
// Traverse the array arr[]
for(int i = 1; i < N; i++)
{
// If previous element is not
// same as current element
if (arr[i] != arr[i - 1])
{
count += 1;
}
}
// Traverse the queries
for(int i = 0; i < Q; i++)
{
// Replace element at
// index x with y
int x = Queries[i][0];
int y = Queries[i][1];
// Recalculate for index x
if (x > 1)
{
// Subtract contribution
// of element at index x
if (arr[x - 1] != arr[x - 2])
{
count -= 1;
}
// Add contribution of y
if (arr[x - 2] != y)
{
count += 1;
}
}
// Recalculate for index x + 1
if (x < N)
{
// Subtract contribution of
// element at index x + 1
if (arr[x] != arr[x - 1])
{
count -= 1;
}
// Adds contribution of y
if (y != arr[x])
{
count += 1;
}
}
System.out.print(count + " ");
// Replace the element
arr[x - 1] = y;
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 1, 2, 5, 2 };
int N = arr.length;
int Q = 2;
int Queries[][] = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
}
}
// This code is contributed by jana_sayantan
Python3
# Python3 program for the above approach def longestSubsequence(N, Q, arr, Queries): count = 1 # Traverse the array arr[] for i in range(1, N): # If previous element is not # same as current element if (arr[i] != arr[i - 1]): count += 1 # Traverse the queries for i in range(Q): # Replace element at # index x with y x = Queries[i][0] y = Queries[i][1] # Recalculate for index x if (x > 1): # Subtract contribution # of element at index x if (arr[x - 1] != arr[x - 2]): count -= 1 # Add contribution of y if (arr[x - 2] != y): count += 1 # Recalculate for index x + 1 if (x < N): # Subtract contribution of # element at index x + 1 if (arr[x] != arr[x - 1]): count -= 1 # Adds contribution of y if (y != arr[x]): count += 1 print(count, end = ' ') # Replace the element arr[x - 1] = y # Driver Code if __name__ == "__main__" : arr = [ 1, 1, 2, 5, 2 ] N = len(arr) Q = 2 Queries = [ [ 1, 3 ], [ 4, 2 ] ] # Function Call longestSubsequence(N, Q, arr, Queries) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
static void longestSubsequence(int N, int Q,
int []arr,
int [,]Queries)
{
int count = 1;
// Traverse the array arr[]
for(int i = 1; i < N; i++)
{
// If previous element is not
// same as current element
if (arr[i] != arr[i - 1])
{
count += 1;
}
}
// Traverse the queries
for(int i = 0; i < Q; i++)
{
// Replace element at
// index x with y
int x = Queries[i, 0];
int y = Queries[i, 1];
// Recalculate for index x
if (x > 1)
{
// Subtract contribution
// of element at index x
if (arr[x - 1] != arr[x - 2])
{
count -= 1;
}
// Add contribution of y
if (arr[x - 2] != y)
{
count += 1;
}
}
// Recalculate for index x + 1
if (x < N)
{
// Subtract contribution of
// element at index x + 1
if (arr[x] != arr[x - 1])
{
count -= 1;
}
// Adds contribution of y
if (y != arr[x])
{
count += 1;
}
}
Console.Write(count + " ");
// Replace the element
arr[x - 1] = y;
}
}
// Driver Code
public static void Main(string []args)
{
int []arr = { 1, 1, 2, 5, 2 };
int N = arr.Length;
int Q = 2;
int [,]Queries = { { 1, 3 }, { 4, 2 } };
// Function Call
longestSubsequence(N, Q, arr, Queries);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// javascript program for the above approach
function longestSubsequence( N , Q , arr , Queries) {
var count = 1;
// Traverse the array arr
for (var i = 1; i < N; i++) {
// If previous element is not
// same as current element
if (arr[i] != arr[i - 1]) {
count += 1;
}
}
// Traverse the queries
for (var i = 0; i < Q; i++) {
// Replace element at
// index x with y
var x = Queries[i][0];
var y = Queries[i][1];
// Recalculate for index x
if (x > 1) {
// Subtract contribution
// of element at index x
if (arr[x - 1] != arr[x - 2]) {
count -= 1;
}
// Add contribution of y
if (arr[x - 2] != y) {
count += 1;
}
}
// Recalculate for index x + 1
if (x < N) {
// Subtract contribution of
// element at index x + 1
if (arr[x] != arr[x - 1]) {
count -= 1;
}
// Adds contribution of y
if (y != arr[x]) {
count += 1;
}
}
document.write(count + " ");
// Replace the element
arr[x - 1] = y;
}
}
// Driver Code
var arr = [ 1, 1, 2, 5, 2 ];
var N = arr.length;
var Q = 2;
var Queries = [ [ 1, 3 ], [ 4, 2 ] ];
// Function Call
longestSubsequence(N, Q, arr, Queries);
// This code contributed by Princi Singh
</script>
Producción:
5 3
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)