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