Longest subsequence with a given OR value : Dynamic Programming Approach | C # 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
using System ; class GFG { static int maxN = 20 ; static int maxM = 64 ; static int [ , ] dp = new int [ maxN , maxM ] ; static bool [ , ] v = new bool [ maxN , maxM ] ; static int findLen ( int [ ] arr , int i , int curr , int n , int m ) { if ( i == n ) { if ( curr == m ) return 0 ; else return - 1 ; } if ( v [ i , curr ] ) return dp [ i , curr ] ; v [ i , curr ] = true ; 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 ] ; } public static void Main ( String [ ] args ) { int [ ] arr = { 3 , 7 , 2 , 3 } ; int n = arr . Length ; int m = 3 ; int ans = findLen ( arr , 0 , 0 , n , m ) ; if ( ans == - 1 ) Console . WriteLine ( 0 ) ; else Console . WriteLine ( ans ) ; } }