Dado un arreglo arr[] de N enteros positivos distintos, denotemos max(i, j) y secondMax(i, j) como el máximo y el segundo elemento máximo del subarreglo arr[i…j] . La tarea es encontrar el valor máximo de max(i, j) XOR secondMax(i, j) para todos los valores posibles de i y j . Tenga en cuenta que el tamaño del subarreglo debe ser al menos dos.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 3
{1, 2}, {2, 3} y {1, 2, 3} son los únicos subarreglos válidos.
Claramente, los valores XOR requeridos son 3, 1 y 1 respectivamente.
Entrada: arr[] = {1, 8, 2}
Salida: 9
Enfoque ingenuo: un enfoque ingenuo será simplemente iterar sobre todos los subarreglos uno por uno y luego encontrar los valores requeridos. Este enfoque requiere una complejidad de tiempo O(N 3 ) .
Enfoque eficiente: Sea arr[i] el segundo elemento máximo de algún subarreglo, entonces el elemento máximo puede ser el primer elemento más grande que arr[i] en dirección hacia adelante o hacia atrás.
Por lo tanto, se puede demostrar que cada elemento, excepto el primero y el último, puede actuar como el segundo elemento máximo como máximo 2 veces solamente. Ahora, simplemente calcule el siguiente elemento mayor de cada elemento en la dirección hacia adelante y hacia atrás y devuelva el XOR máximo de ellos. En este artículo se describe un enfoque para encontrar el siguiente elemento superior mediante pilas .
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 return the maximum possible xor
int maximumXor(int arr[], int n)
{
stack<int> sForward, sBackward;
// To store the final answer
int ans = -1;
for (int i = 0; i < n; i++) {
// forward traversal
while (!sForward.empty()
&& arr[i] < arr[sForward.top()]) {
ans = max(ans, arr[i] ^ arr[sForward.top()]);
sForward.pop();
}
sForward.push(i);
// Backward traversal
while (!sBackward.empty()
&& arr[n - i - 1] < arr[sBackward.top()]) {
ans = max(ans, arr[n - i - 1] ^ arr[sBackward.top()]);
sBackward.pop();
}
sBackward.push(n - i - 1);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 8, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maximumXor(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the maximum possible xor
static int maximumXor(int arr[], int n)
{
Stack<Integer> sForward = new Stack<Integer>(),
sBackward = new Stack<Integer>();
// To store the final answer
int ans = -1;
for (int i = 0; i < n; i++)
{
// forward traversal
while (!sForward.isEmpty()
&& arr[i] < arr[sForward.peek()])
{
ans = Math.max(ans, arr[i] ^ arr[sForward.peek()]);
sForward.pop();
}
sForward.add(i);
// Backward traversal
while (!sBackward.isEmpty()
&& arr[n - i - 1] < arr[sBackward.peek()])
{
ans = Math.max(ans, arr[n - i - 1] ^ arr[sBackward.peek()]);
sBackward.pop();
}
sBackward.add(n - i - 1);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 8, 1, 2 };
int n = arr.length;
System.out.print(maximumXor(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the maximum possible xor def maximumXor(arr: list, n: int) -> int: sForward, sBackward = [], [] # To store the final answer ans = -1 for i in range(n): # forward traversal while len(sForward) > 0 and arr[i] < arr[sForward[-1]]: ans = max(ans, arr[i] ^ arr[sForward[-1]]) sForward.pop() sForward.append(i) # Backward traversal while len(sBackward) > 0 and arr[n - i - 1] < arr[sBackward[-1]]: ans = max(ans, arr[n - i - 1] ^ arr[sBackward[-1]]) sBackward.pop() sBackward.append(n - i - 1) return ans # Driver Code if __name__ == "__main__": arr = [8, 1, 2] n = len(arr) print(maximumXor(arr, n)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the maximum possible xor
static int maximumXor(int []arr, int n)
{
Stack<int> sForward = new Stack<int>(),
sBackward = new Stack<int>();
// To store the readonly answer
int ans = -1;
for (int i = 0; i < n; i++)
{
// forward traversal
while (sForward.Count != 0
&& arr[i] < arr[sForward.Peek()])
{
ans = Math.Max(ans, arr[i] ^ arr[sForward.Peek()]);
sForward.Pop();
}
sForward.Push(i);
// Backward traversal
while (sBackward.Count != 0
&& arr[n - i - 1] < arr[sBackward.Peek()])
{
ans = Math.Max(ans, arr[n - i - 1] ^ arr[sBackward.Peek()]);
sBackward.Pop();
}
sBackward.Push(n - i - 1);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 8, 1, 2 };
int n = arr.Length;
Console.Write(maximumXor(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximum possible xor
function maximumXor(arr, n)
{
let sForward = [];
let sBackward = [];
// To store the readonly answer
let ans = -1;
for (let i = 0; i < n; i++)
{
// forward traversal
while (sForward.length != 0
&& arr[i] < arr[sForward[sForward.length - 1]])
{
ans = Math.max(ans, arr[i] ^ arr[sForward[sForward.length - 1]]);
sForward.pop();
}
sForward.push(i);
// Backward traversal
while (sBackward.length != 0
&& arr[n - i - 1] < arr[sBackward[sBackward.length - 1]])
{
ans = Math.max(ans, arr[n - i - 1] ^ arr[sBackward[sBackward.length - 1]]);
sBackward.pop();
}
sBackward.push(n - i - 1);
}
return ans;
}
let arr = [ 8, 1, 2 ];
let n = arr.length;
document.write(maximumXor(arr, n));
// This code is contributed by rameshtravel07.
</script>
9
Complejidad de tiempo: O(N), ya que estamos usando un ciclo para atravesar la array y el ciclo while interno solo atraviesa N veces, por lo que la complejidad de tiempo efectiva será O(2N).
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para la pila.
Publicación traducida automáticamente
Artículo escrito por AshaRamMeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA