Máximo de XOR del primer y segundo máximo de todos los subarreglos

Dada una array arr[] de elementos distintos, la tarea es encontrar el valor máximo de XOR del primer y segundo elementos máximos de cada subarreglo posible.
Nota: La longitud de la array es mayor que 1. 
Ejemplos: 
 

Entrada: arr[] = {5, 4, 3} 
Salida: 7 
Explicación: 
Todos los posibles subarreglos con una longitud superior a 1 y sus valores XOR del primer y segundo elemento máximo – 
XOR del primer y segundo máximo ({5, 4}) = 1 
XOR del primer y segundo máximo ({5, 4, 3}) = 1 
XOR del primer y segundo máximo ({4, 3}) = 7
Entrada: arr[] = {9, 8, 3, 5, 7 } 
Salida: 15 
 

Enfoque ingenuo: genere todos los subarreglos posibles con una longitud superior a 1 y, para cada subarreglo posible, encuentre el valor XOR del primer y segundo elemento máximo del subarreglo y descubra el valor máximo de ellos.
Enfoque eficiente: para este problema, mantenga una pila y siga los pasos dados: 
 

• Recorra la array dada de izquierda a derecha, luego para cada elemento arr[i] – 
  1. si la parte superior de la pila es menor que arr[i], saque los elementos de la pila hasta que la parte superior de la pila sea menor que arr[i].
  2. Empuje arr[i] en la pila.
  3. Encuentre el valor XOR de los dos elementos superiores de la pila y, si el valor XOR actual es mayor que el máximo encontrado hasta entonces, actualice el valor máximo.

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

// C++ implementation of the above approach.
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the maximum XOR value
int findMaxXOR(vector<int> arr, int n){
     
    vector<int> stack;
    int res = 0, l = 0, i;
 
    // Traversing given array
    for (i = 0; i < n; i++) {
 
        // If there are elements in stack
        // and top of stack is less than
        // current element then pop the elements
        while (!stack.empty() &&
                stack.back() < arr[i]) {
            stack.pop_back();
            l--;
        }
 
        // Push current element
        stack.push_back(arr[i]);
         
        // Increasing length of stack
        l++;
        if (l > 1) {
            // Updating the maximum result
            res = max(res,
             stack[l - 1] ^ stack[l - 2]);
        }
    }
 
 
    return res;
}
 
// Driver Code
int main()
{
    // Initializing array
    vector<int> arr{ 9, 8, 3, 5, 7 };
    int result1 = findMaxXOR(arr, 5);
     
    // Reversing the array(vector)
    reverse(arr.begin(), arr.end());
     
    int result2 = findMaxXOR(arr, 5);
     
    cout << max(result1, result2);
     
    return 0;
}

// Java implementation of the above approach.
import java.util.*;
 
class GFG{
 
// Function to find the maximum XOR value
static int findMaxXOR(Vector<Integer> arr, int n){
     
    Vector<Integer> stack = new Vector<Integer>();
    int res = 0, l = 0, i;
 
    // Traversing given array
    for (i = 0; i < n; i++) {
 
        // If there are elements in stack
        // and top of stack is less than
        // current element then pop the elements
        while (!stack.isEmpty() &&
                stack.get(stack.size()-1) < arr.get(i)) {
            stack.remove(stack.size()-1);
            l--;
        }
 
        // Push current element
        stack.add(arr.get(i));
         
        // Increasing length of stack
        l++;
        if (l > 1) {
             
            // Updating the maximum result
            res = Math.max(res,
            stack.get(l - 1) ^ stack.get(l - 2));
        }
    }
 
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    // Initializing array
    Integer []temp = { 9, 8, 3, 5, 7 };
    Vector<Integer> arr = new Vector<>(Arrays.asList(temp));
    int result1 = findMaxXOR(arr, 5);
     
    // Reversing the array(vector)
    Collections.reverse(arr);
     
    int result2 = findMaxXOR(arr, 5);
     
    System.out.print(Math.max(result1, result2));
}
}
 
// This code is contributed by sapnasingh4991

# Python implementation of the approach
 
from collections import deque
 
 
def maxXOR(arr):
    # Declaring stack
    stack = deque()
     
    # Initializing the length of stack
    l = 0
     
    # Initializing res1 for array
    # traversal of left to right
    res1 = 0
     
    # Traversing the array
    for i in arr:
         
        # If there are elements in stack
        # And top of stack is less than
        # current element then pop the stack
        while stack and stack[-1]<i:
            stack.pop()
            # Simultaneously decrease the
            # length of stack
            l-= 1
     
        # Append the current element
        stack.append(i)
        # Increase the length of stack
        l+= 1
         
        # If there are atleast two elements
        # in stack If xor of top two elements
        # is maximum, we will update the res1
        if l>1:
            res1 = max(res1, stack[-1]^stack[-2])
     
     
    # Similar to the above method,
    # we calculate the xor for reversed array
    res2 = 0
     
    # Clear the whole stack
    stack.clear()
    l = 0
     
    # Reversing the array
    arr.reverse()
    for i in arr:
        while stack and stack[-1]<i:
            stack.pop()
            l-= 1
     
        stack.append(i)
        l+= 1
        if l>1:
            res2 = max(res2, stack[-1]^stack[-2])
             
    # Printing the maximum of res1, res2
    return max(res1, res2)
 
# Driver Code
if __name__ == "__main__":
    # Initializing the array
    arr = [9, 8, 3, 5, 7]
    print(maxXOR(arr))

// C# implementation of the above approach.
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to find the maximum XOR value
static int findMaxXOR(List<int> arr, int n){
      
    List<int> stack = new List<int>();
    int res = 0, l = 0, i;
  
    // Traversing given array
    for (i = 0; i < n; i++) {
  
        // If there are elements in stack
        // and top of stack is less than
        // current element then pop the elements
        while (stack.Count!=0 &&
                stack[stack.Count-1] < arr[i]) {
            stack.RemoveAt(stack.Count-1);
            l--;
        }
  
        // Push current element
        stack.Add(arr[i]);
          
        // Increasing length of stack
        l++;
        if (l > 1) {
              
            // Updating the maximum result
            res = Math.Max(res,
            stack[l - 1] ^ stack[l - 2]);
        }
    }
  
    return res;
}
  
// Driver Code
public static void Main(String[] args)
{
    // Initializing array
    int []temp = { 9, 8, 3, 5, 7 };
    List<int> arr = new List<int>(temp);
    int result1 = findMaxXOR(arr, 5);
      
    // Reversing the array(vector)
    arr.Reverse();
      
    int result2 = findMaxXOR(arr, 5);
      
    Console.Write(Math.Max(result1, result2));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// C++ implementation of the above approach.
 
// Function to find the maximum XOR value
function findMaxXOR(arr, n){
     
    let stack = new Array();
    let res = 0, l = 0, i;
 
    // Traversing given array
    for (i = 0; i < n; i++) {
 
        // If there are elements in stack
        // and top of stack is less than
        // current element then pop the elements
        while (stack.length && stack[stack.length - 1] < arr[i]) {
            stack.pop();
            l--;
        }
 
        // Push current element
        stack.push(arr[i]);
         
        // Increasing length of stack
        l++;
        if (l > 1) {
            // Updating the maximum result
            res = Math.max(res,
            stack[l - 1] ^ stack[l - 2]);
        }
    }
 
 
    return res;
}
 
// Driver Code
 
    // Initializing array
    let arr = [ 9, 8, 3, 5, 7 ];
    let result1 = findMaxXOR(arr, 5);
     
    // Reversing the array(vector)
    arr.reverse();
     
    let result2 = findMaxXOR(arr, 5);
     
    document.write(Math.max(result1, result2));
 
    // This code is contributed by _saurabh_jaiswal
</script>

15