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