Subsecuencia más larga con un valor AND dado – Part 1

Dada una array arr[] y un entero M , la tarea es encontrar la subsecuencia más larga con un valor AND dado M . Si no existe tal subsecuencia, imprima 0 . 
Ejemplos: 
 

Entrada: arr[] = {3, 7, 2, 3}, M = 3 
Salida: 3 
La subsecuencia más larga con valor AND 3 es {3, 7, 3}.
Entrada: arr[] = {2, 2}, M = 3 
Salida: 0 
 

Enfoque: una forma simple de resolver esto será generar todas las subsecuencias posibles y luego encontrar la más grande entre ellas con el valor AND requerido. 
Sin embargo, para valores más pequeños de M , se puede utilizar un enfoque basado en la programación dinámica .
Veamos primero la relación de recurrencia. 
 

dp[i][curr_and] = max(dp[i + 1][curr_and], dp[i + 1][curr_and & arr[i]] + 1) 
 

Comprendamos los estados de DP ahora. Aquí, dp[i][curr_and] almacena la subsecuencia más larga del subarreglo arr[i…N-1] tal que curr_and & AND de esta subsecuencia es igual a M . En cada paso, se puede elegir el índice i actualizando curr_and o se puede rechazar.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 20
#define maxM 64
 
// To store the states of DP
int dp[maxN][maxM];
bool v[maxN][maxM];
 
// Function to return the required length
int findLen(int* arr, int i, int curr,
            int n, int m)
{
    // Base case
    if (i == n) {
        if (curr == m)
            return 0;
        else
            return -1;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][curr])
        return dp[i][curr];
 
    // Setting the state as solved
    v[i][curr] = 1;
 
    // Recurrence relation
    int l = findLen(arr, i + 1, curr, n, m);
    int r = findLen(arr, i + 1, curr & arr[i],
                    n, m);
    dp[i][curr] = l;
    if (r != -1)
        dp[i][curr] = max(dp[i][curr], r + 1);
    return dp[i][curr];
}
 
// Driver code
int main()
{
    int arr[] = { 3, 7, 2, 3 };
    int n = sizeof(arr) / sizeof(int);
    int m = 3;
 
    int ans = findLen(arr, 0, ((1 << 8) - 1),
                      n, m);
    if (ans == -1)
        cout << 0;
    else
        cout << ans;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int maxN = 300;
static int maxM = 300;
 
// To store the states of DP
static int dp[][] = new int[maxN][maxM];
static boolean v[][] = new boolean[maxN][maxM];
 
// Function to return the required length
static int findLen(int[] arr, int i,
                   int curr, int n, int m)
{
    // Base case
    if (i == n)
    {
        if (curr == m)
            return 0;
        else
            return -1;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][curr])
        return dp[i][curr];
 
    // Setting the state as solved
    v[i][curr] = true;
 
    // Recurrence relation
    int l = findLen(arr, i + 1, curr, n, m);
    int r = findLen(arr, i + 1, curr & arr[i], n, m);
    dp[i][curr] = l;
    if (r != -1)
        dp[i][curr] = Math.max(dp[i][curr], r + 1);
    return dp[i][curr];
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 3, 7, 2, 3 };
    int n = arr.length;
    int m = 3;
 
    int ans = findLen(arr, 0, ((1 << 8) - 1), n, m);
    if (ans == -1)
        System.out.print( 0);
    else
        System.out.print( ans);
}
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
import numpy as np
 
maxN = 20
maxM = 256
 
# To store the states of DP
dp = np.zeros((maxN, maxM));
v = np.zeros((maxN, maxM));
 
# Function to return the required length
def findLen(arr, i, curr, n, m) :
 
    # Base case
    if (i == n) :
        if (curr == m) :
            return 0;
        else :
            return -1;
 
    # If the state has been solved before
    # return the value of the state
    if (v[i][curr]) :
        return dp[i][curr];
 
    # Setting the state as solved
    v[i][curr] = 1;
 
    # Recurrence relation
    l = findLen(arr, i + 1, curr, n, m);
    r = findLen(arr, i + 1, curr & arr[i], n, m);
     
    dp[i][curr] = l;
     
    if (r != -1) :
        dp[i][curr] = max(dp[i][curr], r + 1);
         
    return dp[i][curr];
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 3, 7, 2, 3 ];
    n = len(arr);
    m = 3;
 
    ans = findLen(arr, 0, ((1 << 8) - 1), n, m);
     
    if (ans == -1) :
        print(0);
    else :
        print(ans);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
static int maxN = 300;
static int maxM = 300;
 
// To store the states of DP
static int[,] dp = new int[maxN, maxM];
static bool[,] v = new bool[maxN, maxM];
 
// Function to return the required length
static int findLen(int[] arr, int i,
                   int curr, int n, int m)
{
    // Base case
    if (i == n)
    {
        if (curr == m)
            return 0;
        else
            return -1;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i, curr])
        return dp[i, curr];
 
    // Setting the state as solved
    v[i, curr] = true;
 
    // Recurrence relation
    int l = findLen(arr, i + 1, curr, n, m);
    int r = findLen(arr, i + 1, curr & arr[i], n, m);
    dp[i, curr] = l;
    if (r != -1)
        dp[i, curr] = Math.Max(dp[i, curr], r + 1);
    return dp[i, curr];
}
 
// Driver code
public static void Main(String[] args)
{
    int[] arr = { 3, 7, 2, 3 };
    int n = arr.Length;
    int m = 3;
 
    int ans = findLen(arr, 0, ((1 << 8) - 1), n, m);
    if (ans == -1)
        Console.WriteLine(0);
    else
        Console.WriteLine(ans);
}
}
 
// This code is contributed by
// sanjeev2552

<script>
 
// Javascript implementation of the approach
var maxN = 20
var maxM = 64
 
// To store the states of DP
var dp = Array.from(Array(maxN), ()=> Array(maxM));
var v = Array.from(Array(maxN), ()=> Array(maxM));
 
// Function to return the required length
function findLen(arr, i, curr, n, m)
{
    // Base case
    if (i == n) {
        if (curr == m)
            return 0;
        else
            return -1;
    }
 
    // If the state has been solved before
    // return the value of the state
    if (v[i][curr])
        return dp[i][curr];
 
    // Setting the state as solved
    v[i][curr] = 1;
 
    // Recurrence relation
    var l = findLen(arr, i + 1, curr, n, m);
    var r = findLen(arr, i + 1, curr & arr[i],
                    n, m);
    dp[i][curr] = l;
    if (r != -1)
        dp[i][curr] = Math.max(dp[i][curr], r + 1);
    return dp[i][curr];
}
 
// Driver code
var arr = [3, 7, 2, 3];
var n = arr.length;
var m = 3;
var ans = findLen(arr, 0, ((1 << 8) - 1),
                  n, m);
if (ans == -1)
    document.write( 0);
else
    document.write( ans);
 
</script>

3

Complejidad de tiempo: O (N * maxVal) donde maxVal es el elemento máximo de la array dada.

Espacio Auxiliar: O(maxN * maxM)