Find maximum subset | Dp vector ; current element ; current element modulo D ; copy previous state ; Transitions ; return answer ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSum ( vector < int > A , int N , int K , int D ) { vector < vector < vector < int > > > dp ( N + 1 , vector < vector < int > > ( K + 1 , vector < int > ( D + 1 , -1 ) ) ) ; for ( int i = 1 ; i <= N ; i ++ ) { int element = A [ i - 1 ] ; int mod = A [ i - 1 ] % D ; dp [ i ] = dp [ i - 1 ] ; for ( int j = 1 ; j <= K ; j ++ ) { dp [ i ] [ j ] [ mod ] = max ( dp [ i ] [ j ] [ mod ] , element ) ; for ( int p = 0 ; p < D ; p ++ ) { if ( dp [ i - 1 ] [ j - 1 ] [ p ] != -1 ) { dp [ i ] [ j ] [ ( p + mod ) % D ] = max ( dp [ i ] [ j ] [ ( p + mod ) % D ] , dp [ i - 1 ] [ j - 1 ] [ p ] + element ) ; } } } } if ( dp [ N ] [ K ] [ 0 ] == -1 ) return 0 ; return dp [ N ] [ K ] [ 0 ] ; } int main ( ) { int N = 5 , K = 3 , D = 7 ; vector < int > A = { 1 , 11 , 5 , 5 , 18 } ; cout << maximumSum ( A , N , K , D ) << endl ; return 0 ; }