Dada una secuencia arr de N enteros positivos, la tarea es encontrar la longitud de la subsecuencia más larga tal que xor de enteros adyacentes en la subsecuencia no debe ser decreciente .
Ejemplos:
Entrada: N = 8, arr = {1, 100, 3, 64, 0, 5, 2, 15}
Salida: 6
La subsecuencia de longitud máxima es {1, 3, 0, 5, 2, 15}
con XOR de elementos adyacentes como {2, 3, 5, 7, 13}
Entrada: N = 3, arr = {1, 7, 10}
Salida: 3
La subsecuencia de longitud máxima es {1, 3, 7}
con XOR de elementos adyacentes como {2, 4}.
Acercarse:
- Este problema se puede resolver usando programación dinámica donde dp[i] almacenará la longitud de la subsecuencia válida más larga que termina en el índice i .
- Primero, almacene el xor de todos los pares de elementos, es decir, arr[i] ^ arr[j] y el par (i, j) también y luego ordénelos según el valor de xor, ya que deben ser no decrecientes.
- Ahora, si se considera el par (i, j) , entonces la longitud de la subsecuencia más larga que termina en j será max(dp[j], 1 + dp[i]) . De esta manera, calcule el valor máximo posible de la array dp[] para cada posición y luego tome el máximo de ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the longest
// subsequence such that the XOR of adjacent
// elements in the subsequence must
// be non-decreasing
int LongestXorSubsequence(int arr[], int n)
{
vector<pair<int, pair<int, int> > > v;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Computing xor of all the pairs
// of elements and store them
// along with the pair (i, j)
v.push_back(make_pair(arr[i] ^ arr[j],
make_pair(i, j)));
}
}
// Sort all possible xor values
sort(v.begin(), v.end());
int dp[n];
// Initialize the dp array
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// Calculating the dp array
// for each possible position
// and calculating the max length
// that ends at a particular index
for (auto i : v) {
dp[i.second.second]
= max(dp[i.second.second],
1 + dp[i.second.first]);
}
int ans = 1;
// Taking maximum of all position
for (int i = 0; i < n; i++)
ans = max(ans, dp[i]);
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 12, 6, 7, 13, 14, 8, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << LongestXorSubsequence(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
class GFG {
// Function to find the length of the longest
// subsequence such that the XOR of adjacent
// elements in the subsequence must
// be non-decreasing
static int LongestXorSubsequence(int[] arr, int n)
{
List<int[]> v = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Computing xor of all the pairs
// of elements and store them
// along with the pair (i, j)
int[] l1 = { arr[i] ^ arr[j], i, j };
v.add(l1);
}
}
// Sort all possible xor values
Comparator<int[]> byFirstElement
= (int[] a, int[] b) -> a[0] - b[0];
List<int[]> v1 = v.stream()
.sorted(byFirstElement)
.collect(Collectors.toList());
int[] dp = new int[n];
// Initialize the dp array
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// Calculating the dp array
// for each possible position
// and calculating the max length
// that ends at a particular index
Iterator<int[]> iter = v1.iterator();
while (iter.hasNext()) {
int[] list = iter.next();
dp[list[2]]
= Math.max(dp[list[2]], 1 + dp[list[1]]);
}
int ans = 1;
// Taking maximum of all position
for (int i = 0; i < n; i++)
ans = Math.max(ans, dp[i]);
return ans;
}
public static void main(String[] args)
{
// Driver code
int[] arr = { 2, 12, 6, 7, 13, 14, 8, 6 };
int n = arr.length;
System.out.println(LongestXorSubsequence(arr, n));
}
}
// this code is contributed by phasing17
Python3
# Python3 implementation of the approach # Function to find the length of the longest # subsequence such that the XOR of adjacent # elements in the subsequence must # be non-decreasing def LongestXorSubsequence(arr, n): v = [] for i in range(0, n): for j in range(i + 1, n): # Computing xor of all the pairs # of elements and store them # along with the pair (i, j) v.append([(arr[i] ^ arr[j]), (i, j)]) # v.push_back(make_pair(arr[i] ^ arr[j], make_pair(i, j))) # Sort all possible xor values v.sort() # Initialize the dp array dp = [1 for x in range(88)] # Calculating the dp array # for each possible position # and calculating the max length # that ends at a particular index for a, b in v: dp[b[1]] = max(dp[b[1]], 1 + dp[b[0]]) ans = 1 # Taking maximum of all position for i in range(0, n): ans = max(ans, dp[i]) return ans # Driver code arr = [ 2, 12, 6, 7, 13, 14, 8, 6 ] n = len(arr) print(LongestXorSubsequence(arr, n)) # This code is contributed by Sanjit Prasad
C#
// C# implementation of the approach
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Function to find the length of the longest
// subsequence such that the XOR of adjacent
// elements in the subsequence must
// be non-decreasing
static int LongestXorSubsequence(int[] arr, int n)
{
List<int[]> v = new List<int[]>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Computing xor of all the pairs
// of elements and store them
// along with the pair (i, j)
int[] l1 = { arr[i] ^ arr[j], i, j };
v.Add(l1);
}
}
// Sorting the array by First Value
List<int[]> v1 = v.OrderBy(a => a[0])
.ThenBy(a => a[1])
.ToList();
int[] dp = new int[n];
// Initialize the dp array
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// Calculating the dp array
// for each possible position
// and calculating the max length
// that ends at a particular index
foreach(var list in v1) dp[list[2]]
= Math.Max(dp[list[2]], 1 + dp[list[1]]);
int ans = 1;
// Taking maximum of all position
for (int i = 0; i < n; i++)
ans = Math.Max(ans, dp[i]);
return ans;
}
public static void Main(string[] args)
{
// Driver code
int[] arr = { 2, 12, 6, 7, 13, 14, 8, 6 };
int n = arr.Length;
Console.WriteLine(LongestXorSubsequence(arr, n));
}
}
// This code is contributed by phasing17
Javascript
<script>
// Javascript implementation of the approach
// Function to find the length of the longest
// subsequence such that the XOR of adjacent
// elements in the subsequence must
// be non-decreasing
function LongestXorSubsequence(arr, n) {
let v = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Computing xor of all the pairs
// of elements and store them
// along with the pair (i, j)
v.push([arr[i] ^ arr[j], [i, j]]);
}
}
// Sort all possible xor values
v.sort((a, b) => a[0] - b[0]);
let dp = new Array(n);
// Initialize the dp array
for (let i = 0; i < n; i++) {
dp[i] = 1;
}
// Calculating the dp array
// for each possible position
// and calculating the max length
// that ends at a particular index
for (let i of v) {
dp[i[1][1]]
= Math.max(dp[i[1][1]],
1 + dp[i[1][0]]);
}
let ans = 1;
// Taking maximum of all position
for (let i = 0; i < n; i++)
ans = Math.max(ans, dp[i]);
return ans;
}
// Driver code
let arr = [2, 12, 6, 7, 13, 14, 8, 6];
let n = arr.length;
document.write(LongestXorSubsequence(arr, n));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
5
Complejidad temporal: O(N* N)
Espacio auxiliar: O(N)