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