Find maximum subset | Java program for the above approach ; Dp vector ; current element ; current element modulo D ; copy previous state ; Transitions ; return answer ; Driver Code ; Input ; Function call
import java . util . * ; class GFG { static int maximumSum ( int [ ] A , int N , int K , int D ) { int [ ] [ ] [ ] dp = new int [ N + 1 ] [ K + 1 ] [ D + 1 ] ; for ( int i = 0 ; i < N + 1 ; i ++ ) { for ( int j = 0 ; j < K + 1 ; j ++ ) { for ( int k = 0 ; k < D + 1 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 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 ] = Math . 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 ] = Math . 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 ] ; } public static void main ( String [ ] args ) { int N = 5 , K = 3 , D = 7 ; int [ ] A = { 1 , 11 , 5 , 5 , 18 } ; System . out . print ( maximumSum ( A , N , K , D ) ) ; } }