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