Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma máxima de cualquier subsecuencia de la array que tenga AND bit a bit de sus elementos que no sea igual a cero.
Ejemplos:
Entrada: arr[] = {5, 4, 1, 7, 11}
Salida: 24
Explicación:
La subsecuencia con suma máxima es la array completa. AND bit a bit de la array es 0. Por lo tanto, la subsecuencia no se puede considerar.
La subsecuencia con la siguiente suma mayor es {5, 1, 7, 11}. Dado que el AND bit a bit de esta subsecuencia no es cero, la suma de esta subsecuencia (= 24) es la respuesta requerida.
Entrada: arr[] = {5, 6, 2}
Salida: 11
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de la array dada e imprimir la suma máxima de esa subsecuencia que tenga AND bit a bit de todos los elementos de la subsecuencia distintos de cero.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que la suma de solo aquellos elementos cuyos bits están establecidos en todos los elementos de array elegidos da la subsecuencia cuyo AND bit a bit es distinto de cero. Por lo tanto, la idea es maximizar la suma de todos esos elementos. Siga los siguientes pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans , que almacene la suma máxima de subsecuencias que tengan el valor de AND bit a bit como positivo.
- Iterar sobre el rango [0, 32] usando la variable i y realizar los siguientes pasos:
- Inicializa una variable, digamos suma que almacena la suma de todos los elementos cuyo i -ésimo bit está establecido.
- Recorra la array dada y si el i -ésimo bit está establecido en el elemento de la array arr[i] , agregue este valor a la variable sum .
- Actualice el valor de ans al máximo de ans y sum .
- Después de completar los pasos anteriores, imprima el valor de la suma como la suma máxima resultante de la subsecuencia.
A continuación se muestra la implementación de nuestro enfoque:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// a subsequence whose Bitwise AND is non-zero
int maximumSum(int arr[], int N)
{
// Stores the resultant maximum
// sum of the subsequence
int ans = 0;
// Iterate over all the bits
for (int bit = 0; bit < 32; bit++) {
// Stores the sum of array
// elements whose i-th bit is set
int sum = 0;
// Traverse the array elements
for (int i = 0; i < N; i++) {
// If the bit is set, then
// add its value to the sum
if (arr[i] & (1 << bit)) {
sum += arr[i];
}
}
// Update the resultant
// maximum sum
ans = max(ans, sum);
}
// Return the maximum sum
return ans;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 1, 7, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumSum(arr, N);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to find the maximum sum of
// a subsequence whose Bitwise AND is non-zero
static int maximumSum(int arr[], int N)
{
// Stores the resultant maximum
// sum of the subsequence
int ans = 0;
// Iterate over all the bits
for (int bit = 0; bit < 32; bit++) {
// Stores the sum of array
// elements whose i-th bit is set
int sum = 0;
// Traverse the array elements
for (int i = 0; i < N; i++) {
// If the bit is set, then
// add its value to the sum
if ((arr[i] & (1 << bit)) == 1) {
sum += arr[i];
}
}
// Update the resultant
// maximum sum
ans = Math.max(ans, sum);
}
// Return the maximum sum
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 4, 1, 7, 11 };
int N = arr.length;
System.out.println(maximumSum(arr, N));
}
}
// This code is contributed by abhinavjain194
Python3
# python3 program for the above approach # Function to find the maximum sum of # a subsequence whose Bitwise AND is non-zero def maximumSum(arr, N): # Stores the resultant maximum # sum of the subsequence ans = 0 # Iterate over all the bits for bit in range(32): # Stores the sum of array # elements whose i-th bit is set sum = 0 # Traverse the array elements for i in range(N): # If the bit is set, then # add its value to the sum if (arr[i] & (1 << bit)): sum += arr[i] # Update the resultant # maximum sum ans = max(ans, sum) # Return the maximum sum return ans # Driver Code if __name__ == '__main__': arr = [5, 4, 1, 7, 11] N = len(arr) print(maximumSum(arr, N)) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum sum of
// a subsequence whose Bitwise AND is non-zero
static int maximumSum(int[] arr, int N)
{
// Stores the resultant maximum
// sum of the subsequence
int ans = 0;
// Iterate over all the bits
for(int bit = 0; bit < 32; bit++)
{
// Stores the sum of array
// elements whose i-th bit is set
int sum = 0;
// Traverse the array elements
for(int i = 0; i < N; i++)
{
// If the bit is set, then
// add its value to the sum
if ((arr[i] & (1 << bit)) != 0)
{
sum += arr[i];
}
}
// Update the resultant
// maximum sum
ans = Math.Max(ans, sum);
}
// Return the maximum sum
return ans;
}
// Driver code
static public void Main()
{
int[] arr = { 5, 4, 1, 7, 11 };
int N = arr.Length;
Console.Write(maximumSum(arr, N));
}
}
// This code is contributed by offbeat
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum sum of
// a subsequence whose Bitwise AND is non-zero
function maximumSum(arr, N)
{
// Stores the resultant maximum
// sum of the subsequence
let ans = 0;
// Iterate over all the bits
for (let bit = 0; bit < 32; bit++) {
// Stores the sum of array
// elements whose i-th bit is set
let sum = 0;
// Traverse the array elements
for (let i = 0; i < N; i++) {
// If the bit is set, then
// add its value to the sum
if (arr[i] & (1 << bit)) {
sum += arr[i];
}
}
// Update the resultant
// maximum sum
ans = Math.max(ans, sum);
}
// Return the maximum sum
return ans;
}
// Driver Code
let arr = [ 5, 4, 1, 7, 11 ];
let N = arr.length;
document.write(maximumSum(arr, N));
</script>
24
Complejidad de Tiempo: O(N*32)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA