Maximum sum of elements divisible by K from the given array |
#include <bits/stdc++.h> NEW_LINE using namespace std ; int main ( ) { int k = 16 ; vector < int > arr = { 43 , 1 , 17 , 26 , 15 } ; int n = arr . size ( ) ; vector < vector < int > > dp ( n + 2 , vector < int > ( k , 0 ) ) ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 0 ; j < k ; j ++ ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } dp [ i ] [ arr [ i - 1 ] % k ] = max ( dp [ i ] [ arr [ i - 1 ] % k ] , arr [ i - 1 ] ) ; for ( int j = 0 ; j < k ; j ++ ) { int m = ( j + arr [ i - 1 ] ) % k ; if ( dp [ i - 1 ] [ j ] != 0 ) dp [ i ] [ m ] = max ( dp [ i ] [ m ] , arr [ i - 1 ] + dp [ i - 1 ] [ j ] ) ; } } cout << dp [ n ] [ 0 ] ; return 0 ; }