Dada una array A [] de longitud N y un número entero K, la tarea es maximizar el valor de la expresión [ij – K.(A i | A j )] sobre todos los pares (i, j) en la array dada, donde ( 1 ≤ yo < j ≤ N) y | denota operador OR bit a bit .
Ejemplos:
Entrada: A[] = {5, 20, 1, 0, 8, 11}, K = 10
Salida: 2
Explicación: El valor máximo de la expresión f(i, j) = ij – K.(A[i] | A[j]) se puede encontrar para el siguiente par:
f(3, 4) = 3.4 – 10.(1 | 0) = 2Entrada: A[] = {1, 5, 6, 7, 8, 19}, K = 3
Salida: -9
Enfoque: Se deben hacer las siguientes observaciones:
Sea f(i, j) = ij – K.(A i | A j ) .
=> Note que para que f(i, j) sea máxima, ij debe ser máxima y K.(A i | A j ) debe ser mínima.
=> Así, en el mejor de los casos, f(i, j) será máxima si
=> K.(A i | A j ) es igual a 0
=> i = (N-1) y j = N .
=> Entonces, el valor máximo de la expresión puede ser f(i, j) = (N-1)*N .=> Además, el valor mínimo se obtendrá restando el valor máximo de K.(A i | A j ) de (N-1)*N .
=> Se sabe que
un | b < 2*máx(a, b) donde | es el operador OR bit a bit
De la propiedad anterior y las restricciones dadas, se puede inferir:
- El valor máximo de (A i | A j ) puede ser 2*N . porque (0 ≤ A yo ≤ N)
- El valor máximo de K puede ser 100 porque (1 ≤ K ≤ min(N, 100)) .
- Entonces, el valor mínimo de f(i, j) será:
f(i, j) = (N-1)*N – K*(A i | Aj)
= (N-1)*N – 100*2*N
= N*(N – 201)
- Se puede observar fácilmente que la respuesta resultante siempre estará entre:
N*(N-201) <= respuesta <= (N-1)*N
- Además, observe que para i = N – 201 y j = N ,
- el valor máximo de f(i, j) será N*(N – 201) ,
- que a su vez es el valor mínimo de f(i, j) para i = N – 1 y j = N .
- Por lo tanto, el valor máximo de la expresión debe verificarse desde i = N – 201 hasta i = N y j = i+1 hasta j = N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// value of the given expression
long long int maxValue(int N, int K,
long long int A[])
{
// Stores the maximum value of
// the given expression
long long int ans = LLONG_MIN;
// Nested loops to find the maximum
// value of the given expression
for (long long int i = max(0, N - 201);
i < N; ++i) {
for (long long int j = i + 1;
j < N; ++j) {
ans = max(ans, (i + 1) * (j + 1)
- K * (A[i] | A[j]));
}
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Given input
int N = 6, K = 10;
long long int A[N]
= { 5, 20, 1, 0, 8, 11 };
// Function Call
cout << maxValue(N, K, A);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the maximum
// value of the given expression
static int maxValue(int N, int K,
int A[])
{
// Stores the maximum value of
// the given expression
int ans = Integer.MIN_VALUE;
// Nested loops to find the maximum
// value of the given expression
for (int i = Math.max(0, N - 201);
i < N; ++i) {
for (int j = i + 1;
j < N; ++j) {
ans = Math.max(ans, (i + 1) * (j + 1)
- K * (A[i] | A[j]));
}
}
// Return the answer
return ans;
}
// Driver Code
public static void main (String[] args)
{
// Given input
int N = 6, K = 10;
int A[] = { 5, 20, 1, 0, 8, 11 };
// Function Call
System.out.println( maxValue(N, K, A));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python3 program for the above approach LLONG_MIN = -9223372036854775808 # Function to find the maximum # value of the given expression def maxValue(N, K, A): # Stores the maximum value of # the given expression ans = LLONG_MIN # Nested loops to find the maximum # value of the given expression for i in range(max(0, N - 201), N): for j in range(i + 1, N): ans = max(ans, (i + 1) * (j + 1) - K * (A[i] | A[j])) # Return the answer return ans # Driver Code if __name__ == "__main__": # Given input N, K = 6, 10 A = [5, 20, 1, 0, 8, 11] # Function Call print(maxValue(N, K, A)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the maximum
// value of the given expression
static int maxValue(int N, int K,
int []A)
{
// Stores the maximum value of
// the given expression
int ans = Int32.MinValue;
// Nested loops to find the maximum
// value of the given expression
for (int i = Math.Max(0, N - 201);
i < N; ++i) {
for (int j = i + 1;
j < N; ++j) {
ans = Math.Max(ans, (i + 1) * (j + 1)
- K * (A[i] | A[j]));
}
}
// Return the answer
return ans;
}
// Driver Code
public static void Main ()
{
// Given input
int N = 6, K = 10;
int []A = { 5, 20, 1, 0, 8, 11 };
// Function Call
Console.WriteLine(maxValue(N, K, A));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the maximum
// value of the given expression
function maxValue(N, K, A)
{
// Stores the maximum value of
// the given expression
let ans = Number.MIN_VALUE;
// Nested loops to find the maximum
// value of the given expression
for (let i = Math.max(0, N - 201);
i < N; ++i) {
for (let j = i + 1;
j < N; ++j) {
ans = Math.max(ans, (i + 1) * (j + 1)
- K * (A[i] | A[j]));
}
}
// Return the answer
return ans;
}
// Driver Code
// Given input
let N = 6, K = 10;
let A
= [5, 20, 1, 0, 8, 11];
// Function Call
document.write(maxValue(N, K, A));
// This code is contributed by Potta Lokesh
</script>
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA