Maximizar el valor de un par de dos arrays dadas en función de las condiciones dadas

Dados dos arreglos A[] y B[] que consisten en N enteros y un entero K , la tarea es encontrar el valor máximo de B[i] + B[j] + abs(A[i] – A[j]) eligiendo cualquier par (i, j) tal que abs(A[i] – A[j]) ≤ K .

Ejemplos:

Entrada: A[] = {5, 6, 9, 10}, B[] = {3, 0, 10, -10}, K = 1 Salida: 4 Explicación: Solo se pueden elegir dos
pares ,
es
decir (0, 1) y (2, 3), porque abs(A[0] – A[1]) ≤ K y abs(A[2] – A[3]) ≤ K. El valor del par (0, 1)
es B[0] + B[1] + abs(A[0] – A[1]) = 3 + 0 + 1 = 4. El
valor del par (2, 3) es B[2] + B[3] + abs(A[2] – A[3]) = 10 + (-10) + 1 = 1.
Por lo tanto, el valor máximo de todos los pares posibles es 4.

Entrada: A[] = {1, 2, 3, 4}, B[] = {0, 8, 6, 9}, K = 2
Salida: 19

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles a partir de la array dada y contar los pares que satisfacen las condiciones dadas. Después de verificar todos los pares, imprima el conteo de todos los pares.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar árboles de segmentos , búsqueda binaria y clasificación de la array según el valor de la array A[] . Observe que, de la ecuación dada, está claro que B[i] + B[j] + abs(A[i] – A[j]) es igual a cualquiera de los siguientes valores: 

• B[i] + B[j] + (A[i] – A[j])
• B[i] + B[j] + (A[j] – A[i])

Considere la segunda ecuación:

B[i] + B[j] + A[j] – A[i] = B[i] – A[i] + (B[j] + A[j])

• Aquí, se observa que para cada i en la array A[] , encontrar el índice más a la derecha de valor menor que o igual a A[i] + K . Deje que el índice más a la derecha sea correcto .
• Ahora, calcule B[i] – A[i] + valor máximo de B[j] + A[j] donde i + 1 <= j <= right . Esto le dará el valor máximo del par seleccionado.
• Para calcular el valor máximo cada vez en un rango, se pueden usar árboles de segmentos.

Siga los pasos a continuación para resolver el problema:

• Ordene todos los valores, B[i] y B[i] + A[i] según los valores de la array A[] .
• Inicialice maxValue como INT_MIN para almacenar la respuesta máxima final e inicialice un árbol de segmento de consulta de rango máximo que almacene todos los valores, A[i] + B[i] .
• Atraviese la array A[] y realice lo siguiente:
  • Para cada elemento, encuentre el índice, digamos right , tal que abs(A[i] – A[right]) <= K usando Binary Search .
  • Luego, encuentra el valor máximo, de (A[j] + B[j]) donde i+1 <= j <= right .
  • Actualice maxValue como maxValue = max(maxValue, B[i] – A[i] + A[j] + B[j]) .
• Después de los pasos anteriores, imprima el valor de maxValue como resultado.

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

// Java program for the above approach
 
import java.util.*;
 
// Class to store the values of a[i],
// b[i], a[i] + b[i]
class triplet implements Comparable<triplet> {
 
    int a, b, c;
 
    // Constructor
    triplet(int a, int b, int c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }
 
    // Sort values according to array
    public int compareTo(triplet o)
    {
        return this.a - o.a;
    }
}
 
class GFG {
 
    // Stores the segment tree
    static int seg[];
 
    // Function to find the maximum
    // possible value according to the
    // given condition
    public static void maxValue(
        int a[], int b[], int n, int k)
    {
        // Initialize triplet array
        triplet arr[] = new triplet[n];
 
        // Store the values a[i], b[i],
        // a[i] + b[i]
        for (int i = 0; i < n; i++) {
 
            arr[i] = new triplet(a[i], b[i],
                                 a[i] + b[i]);
        }
 
        // Sort the array according
        // to array a[]
        Arrays.sort(arr);
 
        // Build segment tree
        seg = new int[4 * n];
        build(arr, 0, 0, n - 1);
 
        // Initialise the maxvalue of
        // the selected pairs
        int maxvalue = Integer.MIN_VALUE;
 
        // Traverse the array
        for (int i = 0; i < n; i++) {
 
            // For each value find the
            // floor(arr[i] + k)
            int right = search(arr,
                               arr[i].a + k);
 
            // Find the maximum value of
            // the select pairs i and max
            // from (i + 1, right)
            if (right != -1) {
 
                maxvalue = Math.max(
                    maxvalue, arr[i].b - arr[i].a
                                  + getMax(arr, 0, 0, n - 1,
                                           i + 1, right));
            }
        }
 
        // Print the maximum value
        System.out.println(maxvalue);
    }
 
    // Function to search floor of
    // the current value
    public static int search(
        triplet arr[], int val)
    {
        // Initialise low and high values
        int low = 0, high = arr.length - 1;
        int ans = -1;
 
        // Perform Binary Search
        while (low <= high) {
            int mid = low + (high - low) / 2;
 
            // If the current value is
            // <= val then store the
            // candidate answer and
            // find for rightmost one
            if (arr[mid].a <= val) {
                ans = mid;
                low = mid + 1;
            }
            else
                high = mid - 1;
        }
        return ans;
    }
 
    // Function to build segment tree
    public static void build(
        triplet arr[], int index,
        int s, int e)
    {
        // Base Case
        if (s == e) {
            seg[index] = arr[s].c;
            return;
        }
        int mid = s + (e - s) / 2;
 
        // Build the left and right
        // segment trees
        build(arr, 2 * index + 1, s, mid);
        build(arr, 2 * index + 2, mid + 1, e);
 
        // Update current index
        seg[index] = Math.max(seg[2 * index + 1],
                              seg[2 * index + 2]);
    }
 
    // Function to get maximum value
    // in the range [qs, qe]
    public static int getMax(
        triplet arr[], int index, int s,
        int e, int qs, int qe)
    {
        // If segment is not in range
        if (qe < s || e < qs)
            return Integer.MIN_VALUE / 2;
 
        // If segment is completely
        // inside the query
        if (s >= qs && e <= qe)
            return seg[index];
 
        // Calculate the maximum value
        // in left and right half
        int mid = s + (e - s) / 2;
        return Math.max(
            getMax(arr, 2 * index + 1,
                   s, mid, qs, qe),
            getMax(arr, 2 * index + 2,
                   mid + 1, e, qs, qe));
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 4, K = 1;
        int A[] = { 5, 6, 9, 10 };
        int B[] = { 3, 0, 10, -10 };
 
        // Function call
        maxValue(A, B, N, K);
    }
}

// C# program for the above approach
using System;
using System.Collections.Generic;
 
// Class to store the values of a[i],
// b[i], a[i] + b[i]
public class triplet : IComparable<triplet> {
 
    public int a, b, c;
 
    // Constructor
    public triplet(int a, int b, int c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }
 
    // Sort values according to array
    public int CompareTo(triplet o)
    {
        return this.a - o.a;
    }
}
 
public class GFG {
 
    // Stores the segment tree
    static int []seg;
 
    // Function to find the maximum
    // possible value according to the
    // given condition
    public  void maxValue(
        int []a, int []b, int n, int k)
    {
        // Initialize triplet array
        triplet []arr = new triplet[n];
 
        // Store the values a[i], b[i],
        // a[i] + b[i]
        for (int i = 0; i < n; i++) {
 
            arr[i] = new triplet(a[i], b[i],
                                 a[i] + b[i]);
        }
 
        // Sort the array according
        // to array []a
        Array.Sort(arr);
 
        // Build segment tree
        seg = new int[4 * n];
        build(arr, 0, 0, n - 1);
 
        // Initialise the maxvalue of
        // the selected pairs
        int maxvalue = int.MinValue;
 
        // Traverse the array
        for (int i = 0; i < n; i++) {
  
            // For each value find the
            // floor(arr[i] + k)
            int right = search(arr,
                               arr[i].a + k);
 
            // Find the maximum value of
            // the select pairs i and max
            // from (i + 1, right)
            if (right != -1) {
 
                maxvalue = Math.Max(
                    maxvalue, arr[i].b - arr[i].a
                                  + getMax(arr, 0, 0, n - 1,
                                           i + 1, right));
            }
        }
 
        // Print the maximum value
        Console.WriteLine(maxvalue);
    }
 
    // Function to search floor of
    // the current value 
    public int search(
        triplet []arr, int val)
    {
        // Initialise low and high values
        int low = 0, high = arr.Length - 1;
        int ans = -1;
 
        // Perform Binary Search
        while (low <= high) {
            int mid = low + (high - low) / 2;
 
            // If the current value is
            // <= val then store the
            // candidate answer and
            // find for rightmost one
            if (arr[mid].a <= val) {
                ans = mid;
                low = mid + 1;
            }
            else
                high = mid - 1;
        }
        return ans;
    }
 
    // Function to build segment tree
    public static void build(
        triplet []arr, int index,
        int s, int e)
    {
        // Base Case
        if (s == e) {
            seg[index] = arr[s].c;
            return;
        }
        int mid = s + (e - s) / 2;
 
        // Build the left and right
        // segment trees
        build(arr, 2 * index + 1, s, mid);
        build(arr, 2 * index + 2, mid + 1, e);
 
        // Update current index
        seg[index] = Math.Max(seg[2 * index + 1],
                              seg[2 * index + 2]);
    }
 
    // Function to get maximum value
    // in the range [qs, qe]
    public static int getMax(
        triplet []arr, int index, int s,
        int e, int qs, int qe)
    {
        // If segment is not in range
        if (qe < s || e < qs)
            return int.MinValue / 2;
 
        // If segment is completely
        // inside the query
        if (s >= qs && e <= qe)
            return seg[index];
 
        // Calculate the maximum value
        // in left and right half
        int mid = s + (e - s) / 2;
        return Math.Max(
            getMax(arr, 2 * index + 1,
                   s, mid, qs, qe),
            getMax(arr, 2 * index + 2,
                   mid + 1, e, qs, qe));
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        int N = 4, K = 1;
        int []A = { 5, 6, 9, 10 };
        int []B = { 3, 0, 10, -10 };
 
        // Function call
        new GFG().maxValue(A, B, N, K);
    }
}
 
// This code is contributed by 29AjayKumar

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)