Maximice la subsecuencia XOR posible mediante elementos equidistantes de ambos extremos

Dada una array A[] de tamaño N , encuentre la subsecuencia Xor máxima tal que tanto A [ i ] como A [ N – i – 1 ] pertenezcan a esta subsecuencia, donde i oscila entre [0, N – 1] .

Ejemplos:

Entrada: N = 8, A [ ] = {1, 2, 3, 4, 5, 6, 7, 8}
Salida: 13
Explicación:
La subsecuencia Xor máxima es {1, 3, 4, 5, 6, 8}

Entrada: N = 5, A [ ] = {3, 2, 6, 5, 4}
Salida: 6
Explicación:
La subsecuencia Xor máxima es {3, 2, 6, 5, 4}

Enfoque:
dado que tanto A[i] como A[Ni-1] deben estar presentes en la misma subsecuencia, emparéjelos y luego encuentre la suma xor máxima. Para cada índice válido i , calcule (A[i] ^ A[Ni-1]) y guárdelo en la nueva array X . El tamaño de esta nueva array será N/2.

Solución ingenua:
el enfoque más simple después de crear la array X[] para este problema es generar recursivamente todas las subsecuencias de X y encontrar la subsecuencia xor máxima.

La siguiente es la definición recursiva de maxXorSubseq(X, N, i):

maxXorSubseq ( X, N, i ) = MAX ( X[ i ] ^ maxXorSubseq ( X, N, i + 1 ), maxXorSubseq (X, N, i + 1) )

El total de combinaciones posibles será 2 ^N .
Complejidad del tiempo: O(2 ^N )

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation
// of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Returns maximum xor
int maxXorSubseq(vector<int> &x, int n,
                                 int i)
{
    if(i == n)
       return 0;
 
    return max(x[i] ^ maxXorSubseq(x, n,
                                   i + 1),
                      maxXorSubseq(x, n,
                                   i + 1));
}
 
vector<int> compute(vector<int> a, int n)
{
    vector<int> x;
 
    // Calculate a[i]^a[n-i-1]
    for(int i = 0; i < n / 2; i++)
       x.push_back(a[i] ^ a[n - i - 1]);
 
    // If n is odd
    if(n & 1)
       x.push_back(a[n / 2]);
 
    return x;
}
 
// Driver code
int main()
{
    int n = 8;
    vector<int> a = { 1, 2, 3, 4,
                      5, 6, 7, 8 };
     
    // Getting new array x
    vector<int> x = compute(a, n);
     
    int mxXor = maxXorSubseq(x, x.size(), 0);
     
    cout << (mxXor);
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java implementation
// of the above approach
import java.util.*;
 
class GFG{
 
// Returns maximum xor
static int maxXorSubseq(List<Integer> x, int n,
                                         int i)
{
    if(i == n)
    return 0;
 
    return Math.max(x.get(i) ^ maxXorSubseq(x, n,
                                            i + 1),
                               maxXorSubseq(x, n,
                                            i + 1));
}
 
static List<Integer> compute(List<Integer> a, int n)
{
    List<Integer> x = new ArrayList<Integer>();
 
    // Calculate a[i]^a[n-i-1]
    for(int i = 0; i < n / 2; i++)
        x.add(a.get(i) ^ a.get(n - i - 1));
 
    // If n is odd
    if((n & 1) == 1)
        x.add(a.get(n / 2));
 
    return x;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 8;
    List<Integer> a = Arrays.asList( 1, 2, 3, 4,
                                     5, 6, 7, 8 );
     
    // Getting new array x
    List<Integer> x = compute(a, n);
     
    int mxXor = maxXorSubseq(x, x.size(), 0);
     
    System.out.println((mxXor));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 implementation
# of the above approach
 
# Returns maximum xor
def maxXorSubseq(x, n, i):
     
    if(i == n):
        return 0
         
    return max(
        x[i]^maxXorSubseq(
        x, n, i + 1), maxXorSubseq(
        x, n, i + 1))
 
def compute(a, n):
     
    x = []
     
    # Calculate a[i]^a[n-i-1]
    for i in range(n//2):    
        x.append(a[i]^a[n-i-1])
     
    # If n is odd
    if(n&1):
        x.append(a[n//2])
         
    return x
 
# Driver code
if __name__ =="__main__":
     
    n = 8
    a = [1, 2, 3, 4, 5, 6, 7, 8]
     
    # Getting new array x
    x = compute(a, n)
     
    mxXor = maxXorSubseq(x, len(x), 0)
     
    print(mxXor)

C#

// C# implementation 
// of the above approach 
using System;
using System.Collections.Generic;
class GFG {
     
    // Returns maximum xor
    static int maxXorSubseq(List<int> x, int n, int i)
    {
        if(i == n)
        return 0;
       
        return Math.Max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, i + 1));
    }
       
    static List<int> compute(List<int> a, int n)
    {
        List<int> x = new List<int>();
       
        // Calculate a[i]^a[n-i-1]
        for(int i = 0; i < n / 2; i++)
            x.Add(a[i] ^ a[n - i - 1]);
       
        // If n is odd
        if((n & 1) == 1)
            x.Add(a[n / 2]);
       
        return x;
    }
 
  static void Main() {
        int n = 8;
        List<int> a = new List<int>{ 1, 2, 3, 4, 5, 6, 7, 8 };
           
        // Getting new array x
        List<int> x = compute(a, n);
           
        int mxXor = maxXorSubseq(x, x.Count, 0);
           
        Console.WriteLine((mxXor));
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
    // Javascript implementation
    // of the above approach
     
    // Returns maximum xor
    function maxXorSubseq(x, n, i)
    {
        if(i == n)
        return 0;
        
        return Math.max(x[i] ^ maxXorSubseq(x, n, i + 1),
        maxXorSubseq(x, n, i + 1));
    }
        
    function compute(a, n)
    {
        let x = [];
        
        // Calculate a[i]^a[n-i-1]
        for(let i = 0; i < parseInt(n / 2, 10); i++)
            x.push(a[i] ^ a[n - i - 1]);
        
        // If n is odd
        if((n & 1) == 1)
            x.push(a[parseInt(n / 2, 10)]);
        
        return x;
    }
     
    let n = 8;
    let a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
 
    // Getting new array x
    let x = compute(a, n);
 
    let mxXor = maxXorSubseq(x, x.length, 0);
 
    document.write((mxXor));
 
</script>

Producción:

Complejidad del tiempo: O(2 ⁿ )

Espacio Auxiliar: O(N)

Enfoque eficiente: teniendo
en cuenta la implementación anterior, el siguiente es un árbol de recurrencia parcial para la entrada X = [9, 5, 1]

En el árbol de recursión parcial anterior, maxXorSubseq({1}) se resuelve cuatro veces. Al dibujar el árbol de recursión completo, se puede observar que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene subproblemas superpuestos y el recálculo de los mismos subproblemas se puede evitar mediante Memoization .

Para la memorización, cree una array dp [ ] y almacene:

dp[i] = max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, idx + 1)

Esto evita el recálculo de índices previamente calculados, optimizando así la complejidad computacional.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
vector<int> dp;
  
// Returns maximum xor sum
int maxXorSubseq(vector<int> x, int n, int idx)
{
    if (idx == n)
    {
        return 0;
    }
      
    // If already precomputed
    if (dp[idx] != -1)
    {
        return dp[idx];
    }
    int ans = 0;
    ans = max(ans, x[idx] ^ maxXorSubseq(x, n, idx + 1));
    ans = max(ans, maxXorSubseq(x, n, idx + 1));
                     
    // Store the maximum
    dp[idx] = ans;
    return ans;
}
  
vector<int> compute(int a[],int n)
{
    vector<int> x;
      
    // Calculate a[i]^a[n-i-1]
    for(int i = 0; i < n / 2; i++)
    {
        x.push_back(a[i] ^ a[n - i - 1]);
    }
      
    //  If n is odd
    if ((n & 1) != 0)
    {
        x.push_back(a[n / 2]);
    }
    return x;
}
 
// Driver code
int main()
{
    int n = 8;
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
      
    // Getting new array x
    vector<int> x = compute(a, n);
      
    // Initialize dp array
    for(int i = 0; i < x.size(); i++)
    {
        dp.push_back(-1);
    }
    int mxXor = maxXorSubseq(x, x.size(), 0);    
    cout << mxXor << endl;
    return 0;
}
 
// This code is contributed by divyesh072019.

Java

// Java implementation of the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
static Vector<Integer> dp = new Vector<Integer>();
 
// Returns maximum xor sum
static int maxXorSubseq(Vector<Integer> x,
                        int n, int idx)
{
    if (idx == n)
    {
        return 0;
    }
     
    // If already precomputed
    if (dp.get(idx) != -1)
    {
        return dp.get(idx);
    }
    int ans = 0;
    ans = Math.max(ans, x.get(idx) ^
                   maxXorSubseq(x, n, idx + 1));
    ans = Math.max(ans,
                   maxXorSubseq(x, n, idx + 1));
                    
    // Store the maximum
    dp.set(idx,ans);
    return ans;
}
 
static Vector<Integer> compute(int[] a,int n)
{
    Vector<Integer> x = new Vector<Integer>();
     
    // Calculate a[i]^a[n-i-1]
    for(int i = 0; i < n / 2; i++)
    {
        x.add(a[i] ^ a[n - i - 1]);
    }
     
    //  If n is odd
    if ((n & 1) != 0)
    {
        x.add(a[n / 2]);
    }
    return x;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 8;
    int[] a = { 1, 2, 3, 4, 5, 6, 7, 8 };
     
    // Getting new array x
    Vector<Integer> x = compute(a, n);
     
    // Initialize dp array
    for(int i = 0; i < x.size(); i++)
    {
        dp.add(-1);
    }
    int mxXor = maxXorSubseq(x, x.size(), 0);
     
    System.out.println(mxXor);
}
}
 
//  This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation
# of the above approach
 
# Returns maximum xor sum
def maxXorSubseq(x, n, idx):
     
    if(idx == n):
        return 0
         
    # If already precomputed
    if(dp[idx]!=-1):
        return dp[idx]
 
    ans = 0
     
    ans = max(
        ans, x[idx] ^ maxXorSubseq(
                    x, n, idx + 1))
     
    ans = max(ans, maxXorSubseq(
                    x, n, idx + 1))
     
    # Store the maximum
    dp[idx] = ans
     
    return ans
 
def compute(a, n):
     
    x = []
     
    # Calculate a[i]^a[n-i-1]
    for i in range(n//2):
        x.append(a[i]^a[n-i-1])
     
    # If n is odd
    if(n&1):
        x.append(a[n//2])
         
    return x
     
# Declared dp[] array globally
dp = []
 
# Driver code
if __name__ =="__main__":
     
    n = 8
    a =[1, 2, 3, 4, 5, 6, 7, 8]
     
    # Getting new array x
    x = compute(a, n)
 
    # Initialize dp array
    dp = [-1 for i in range(len(x))]
     
    mxXor = maxXorSubseq(x, len(x), 0)
     
    print(mxXor)

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
    static List<int> dp = new List<int>();
   
    // Returns maximum xor sum
    static int maxXorSubseq(List<int> x, int n, int idx)
    {
        if (idx == n)
        {
            return 0;
        }
       
        // If already precomputed
        if(dp[idx] != -1)
        {
            return dp[idx];
        }
        int ans = 0;
        ans = Math.Max(ans, x[idx]^maxXorSubseq(x, n, idx + 1));
        ans = Math.Max(ans, maxXorSubseq(x, n, idx + 1));
       
        // Store the maximum
        dp[idx] = ans;
        return ans;
    }
    static List<int> compute(int[] a,int n)
    {
        List<int> x = new List<int>();
       
        // Calculate a[i]^a[n-i-1]
        for(int i = 0; i < n / 2; i++)
        {
            x.Add(a[i] ^ a[n - i - 1]);
        }
       
        //  If n is odd
        if((n & 1) != 0)
        {
            x.Add(a[n / 2]);
        }
        return x;
    }
   
    // Driver code
    static public void Main ()
    {
        int n = 8;
        int[] a = { 1, 2, 3, 4, 5, 6, 7, 8 };
       
        // Getting new array x
        List<int> x = compute(a, n);
       
        // Initialize dp array
        for(int i = 0; i < x.Count; i++)
        {
            dp.Add(-1);
        }
        int mxXor = maxXorSubseq(x, x.Count, 0);
        Console.WriteLine(mxXor);
    }
}
 
// This code is contributed by rag2127

Javascript

<script>
    // Javascript implementation of the above approach
     
    let dp = [];
    
    // Returns maximum xor sum
    function maxXorSubseq(x, n, idx)
    {
        if (idx == n)
        {
            return 0;
        }
        
        // If already precomputed
        if(dp[idx] != -1)
        {
            return dp[idx];
        }
        let ans = 0;
        ans = Math.max(ans, x[idx]^maxXorSubseq(x, n, idx + 1));
        ans = Math.max(ans, maxXorSubseq(x, n, idx + 1));
        
        // Store the maximum
        dp[idx] = ans;
        return ans;
    }
     
    function compute(a, n)
    {
        let x = [];
        
        // Calculate a[i]^a[n-i-1]
        for(let i = 0; i < parseInt(n / 2, 10); i++)
        {
            x.push(a[i] ^ a[n - i - 1]);
        }
        
        //  If n is odd
        if((n & 1) != 0)
        {
            x.push(a[n / 2]);
        }
        return x;
    }
     
    let n = 8;
    let a = [ 1, 2, 3, 4, 5, 6, 7, 8 ];
 
    // Getting new array x
    let x = compute(a, n);
 
    // Initialize dp array
    for(let i = 0; i < x.length; i++)
    {
      dp.push(-1);
    }
    let mxXor = maxXorSubseq(x, x.length, 0);
    document.write(mxXor);
 
 
// This code is contributed by suresh07.
</script>

Producción:

Complejidad del tiempo: O(N)

Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por ghoshashis545 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta