Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud de la subsecuencia par absoluta creciente más larga.
Una subsecuencia par absoluta creciente es una subsecuencia creciente de elementos de array que tienen una diferencia absoluta entre pares adyacentes como pares.
Ejemplos:
Entrada: arr[] = {10, 22, 9, 33, 21, 50, 41, 60}
Salida: 4
Explicación: La subsecuencia par absoluta creciente más larga es {10, 22, 50, 60}. Por lo tanto, la longitud requerida es 4.Entrada: arr[] = {11, -22, 43, -54, 66, 5}
Salida: 3
Explicación:
La subsecuencia par absoluta creciente más larga es 3, es decir, {-22, -54, 66}. Por lo tanto, la longitud requerida es 4.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la array dada y, para cada subsecuencia, verificar si la subsecuencia aumenta y si la diferencia absoluta entre los elementos adyacentes es uniforme o no. Imprime la longitud de la subsecuencia más larga.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es similar a encontrar la subsecuencia creciente más larga . Pero la única condición a cambiar es verificar si la diferencia absoluta entre dos elementos adyacentes de la subsecuencia es par o no. Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar dp[] donde todos son inicialmente 1 .
- Recorra la array dada arr[] usando la variable i sobre el rango [0, N) , y para cada índice haga lo siguiente:
- Itere usando la variable j sobre el rango [0, i) y verifique las siguientes tres condiciones:
- Si el valor absoluto de arr[i] > arr[j] .
- Si arr[i] y arr[j] son pares o no.
- Si dp[i] < dp[j] + 1 .
- Si las tres condiciones anteriores se cumplen para cualquier índice j , actualice dp[i] = dp[j] + 1 .
- Itere usando la variable j sobre el rango [0, i) y verifique las siguientes tres condiciones:
- Imprime el elemento máximo de la array dp[] como el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest // increasing absolute even subsequence void EvenLIS(int arr[], int n) { // Stores length of // required subsequence int lis[n]; for(int i = 0; i < n; i++) lis[i] = 1; // Traverse the array for(int i = 1; i < n; i++) { // Traverse prefix of current // array element for(int j = 0; j < i; j++) { // Check if the subsequence is // LIS and have even absolute // difference of adjacent pairs if (abs(arr[i]) > abs(arr[j]) && abs(arr[i]) % 2 == 0 && abs(arr[j]) % 2 == 0 && lis[i] < lis[j] + 1) // Update lis[] lis[i] = lis[j] + 1; } } // Stores maximum length int maxlen = 0; // Find the length of longest // absolute even subsequence for(int i = 0; i < n; i++) maxlen = max(maxlen, lis[i]); // Return the maximum length of // absolute even subsequence cout << maxlen << endl; } // Driver code int main() { // Given array arr[] and brr[] int arr[] = { 11, -22, 43, -54, 66, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call EvenLIS(arr, N); } // This code is contributed by code_hunt
Java
// Java program for the above approach import java.util.*; import java.io.*; class GFG{ // Function to find the longest // increasing absolute even subsequence static void EvenLIS(int arr[]) { // Length of arr int n = arr.length; // Stores length of // required subsequence int lis[] = new int[n]; Arrays.fill(lis, 1); // Traverse the array for(int i = 1; i < n; i++) { // Traverse prefix of current // array element for(int j = 0; j < i; j++) { // Check if the subsequence is // LIS and have even absolute // difference of adjacent pairs if (Math.abs(arr[i]) > Math.abs(arr[j]) && Math.abs(arr[i]) % 2 == 0 && Math.abs(arr[j]) % 2 == 0 && lis[i] < lis[j] + 1) // Update lis[] lis[i] = lis[j] + 1; } } // Stores maximum length int maxlen = 0; // Find the length of longest // absolute even subsequence for(int i = 0; i < n; i++) maxlen = Math.max(maxlen, lis[i]); // Return the maximum length of // absolute even subsequence System.out.println(maxlen); } // Driver code public static void main(String args[]) { // Given array arr[] and brr[] int arr[] = { 11, -22, 43, -54, 66, 5 }; int N = arr.length; // Function call EvenLIS(arr); } } // This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach # Function to find the longest # increasing absolute even subsequence def EvenLIS(arr): # Length of arr n = len(arr) # Stores length of # required subsequence lis = [1]*n # Traverse the array for i in range(1, n): # Traverse prefix of current # array element for j in range(0, i): # Check if the subsequence is # LIS and have even absolute # difference of adjacent pairs if abs(arr[i]) > abs(arr[j]) \ and abs(arr[i] % 2) == 0 \ and abs(arr[j] % 2) == 0 \ and lis[i] < lis[j]+1: # Update lis[] lis[i] = lis[j]+1 # Stores maximum length maxlen = 0 # Find the length of longest # absolute even subsequence for i in range(n): maxlen = max(maxlen, lis[i]) # Return the maximum length of # absolute even subsequence print(maxlen) # Driver Code # Given arr[] arr = [11, -22, 43, -54, 66, 5] # Function Call EvenLIS(arr)
C#
// C# program for the above approach using System; class GFG{ // Function to find the longest // increasing absolute even subsequence static void EvenLIS(int []arr) { // Length of arr int n = arr.Length; // Stores length of // required subsequence int []lis = new int[n]; for(int i = 0; i < n; i++) lis[i] = 1; // Traverse the array for(int i = 1; i < n; i++) { // Traverse prefix of current // array element for(int j = 0; j < i; j++) { // Check if the subsequence is // LIS and have even absolute // difference of adjacent pairs if (Math.Abs(arr[i]) > Math.Abs(arr[j]) && Math.Abs(arr[i]) % 2 == 0 && Math.Abs(arr[j]) % 2 == 0 && lis[i] < lis[j] + 1) // Update lis[] lis[i] = lis[j] + 1; } } // Stores maximum length int maxlen = 0; // Find the length of longest // absolute even subsequence for(int i = 0; i < n; i++) maxlen = Math.Max(maxlen, lis[i]); // Return the maximum length of // absolute even subsequence Console.WriteLine(maxlen); } // Driver code public static void Main(String []args) { // Given array []arr and brr[] int []arr = { 11, -22, 43, -54, 66, 5 }; int N = arr.Length; // Function call EvenLIS(arr); } } // This code is contributed by Amit Katiyar
Javascript
<script> // Javascript program to implement // the above approach // Function to find the longest // increasing absolute even subsequence function EvenLIS(arr) { // Length of arr let n = arr.length; // Stores length of // required subsequence let lis = new Array(n).fill(1); // Traverse the array for(let i = 1; i < n; i++) { // Traverse prefix of current // array element for(let j = 0; j < i; j++) { // Check if the subsequence is // LIS and have even absolute // difference of adjacent pairs if (Math.abs(arr[i]) > Math.abs(arr[j]) && Math.abs(arr[i]) % 2 == 0 && Math.abs(arr[j]) % 2 == 0 && lis[i] < lis[j] + 1) // Update lis[] lis[i] = lis[j] + 1; } } // Stores maximum length let maxlen = 0; // Find the length of longest // absolute even subsequence for(let i = 0; i < n; i++) maxlen = Math.max(maxlen, lis[i]); // Return the maximum length of // absolute even subsequence document.write(maxlen); } // Driver Code // Given array arr[] and brr[] let arrr = [ 11, -22, 43, -54, 66, 5 ]; let N = arrr.length; // Function call EvenLIS(arrr); </script>
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA