Encuentre subsecuencias con el máximo Bitwise AND y Bitwise OR

Dada una array de n elementos. La tarea es imprimir la suma máxima seleccionando dos subsecuencias de la array (no necesariamente diferentes) de modo que la suma de AND bit a bit de todos los elementos de la primera subsecuencia y OR bit a bit de todos los elementos de la segunda subsecuencia sea máxima. 

Ejemplos:

Input: arr[] = {3, 5, 6, 1}
Output: 13
We get maximum AND value by choosing 6 only and maximum OR value by choosing all (3 | 5 | 6 | 1) = 7. So the result is 6 + 7 = 13.

Input: arr[] = {3, 3}
Output: 6

Enfoque: El OR máximo sería el o de todos los números y el AND máximo sería el elemento máximo en la array. Esto es así porque si (x | y) >= x, y y (x & y) <=x, y. 
 

//C++ implementation of above approach
#include<bits/stdc++.h>
 
using namespace std;
 
//function to find the maximum sum
void maxSum(int a[],int n)
{
    int maxAnd=0;
     
    //Maximum And is maximum element
    for(int i=0;i<n;i++)
        maxAnd=max(maxAnd,a[i]);
     
    //Maximum OR is bitwise OR of all
    int maxOR=0;
    for(int i=0;i<n;i++)
    {
        maxOR=maxOR|a[i];
    }
     
    cout<<maxAnd+maxOR;
}
 
//Driver code
int main()
{
    int a[]={3,5,6,1};
     
    int n=sizeof(a)/sizeof(a[0]);
     
    maxSum(a,n);
}
 
//This code is contributed by Mohit kumar 29

import java.util.Arrays;
 
// Java implementation of the above approach
// Function to find the maximum sum
class GFG {
 
    static void maxSum(int[] a, int n) {
 
        // Maximum AND is maximum element
        int maxAnd = Arrays.stream(a).max().getAsInt();
 
        // Maximum OR is bitwise OR of all.
        int maxOR = 0;
        for (int i = 0; i < n; i++) {
            maxOR |= a[i];
        }
        System.out.println((maxAnd + maxOR));
 
// Driver code
    }
 
    public static void main(String[] args) {
 
        int n = 4;
        int[] a = {3, 5, 6, 1};
        maxSum(a, n);
    }
}
 
//This code contributed by 29AjayKumar

# Python implementation of the above approach
 
# Function to find the maximum sum
def maxSum(a, n):
 
    # Maximum AND is maximum element
    maxAnd = max(a)
 
    # Maximum OR is bitwise OR of all.
    maxOR = 0
    for i in range(n):
        maxOR|= a[i]
         
    print(maxAnd + maxOR)
 
# Driver code
n = 4
a = [3, 5, 6, 1]
maxSum(a, n)

// C# implementation of the above approach
 
using System;
using System.Linq;
public class GFG {
      
    // Function to find the maximum sum
    static void maxSum(int []a, int n) {
  
        // Maximum AND is maximum element
        int maxAnd = a.Max();
        // Maximum OR is bitwise OR of all.
        int maxOR = 0;
        for (int i = 0; i < n; i++) {
            maxOR |= a[i];
        }
        Console.Write((maxAnd + maxOR));
  
// Driver code
    }
  
    public static void Main() {
  
        int n = 4;
        int[] a = {3, 5, 6, 1};
        maxSum(a, n);
    }
}
  
//This code contributed by 29AjayKumar

<?php
// PHP implementation of the
// above approach
 
// Function to find the maximum sum
function maxSum($a, $n)
{
 
    // Maximum AND is maximum element
    $maxAnd = max($a);
 
    // Maximum OR is bitwise OR of all.
    $maxOR = 0;
    for($i = 0; $i < $n; $i++)
        $maxOR|= $a[$i];
         
    print($maxAnd + $maxOR);
}
 
// Driver code
$n = 4;
$a = array(3, 5, 6, 1);
maxSum($a, $n);
 
// This code is contributed by mits
?>

<script>
 
// Javascript implementation of the above approach
 
// Function to find the maximum sum
function maxSum(a, n)
{
 
    // Maximum AND is maximum element
    var maxAnd = Math.max(...a);
     
    // Maximum OR is bitwise OR of all.
    var maxOR = 0;
    for(var i = 0; i < n; i++)
    {
        maxOR |= a[i];
    }
    document.write((maxAnd + maxOR));
}
 
// Driver code
var n = 4;
var a = [ 3, 5, 6, 1];
 
maxSum(a, n);
 
// This code is contributed by Ankita saini
 
</script>

13

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)