Maximum sum of elements divisible by K from the given array |  ; Function to return the maximum sum divisible by k from elements of v ; check if sum of elements excluding the current one is divisible by k ; check if sum of elements including the current one is divisible by k ; Store the maximum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 1001 ] [ 1001 ] ; int find_max ( int i , int sum , vector < int > & v , int k ) { if ( i == v . size ( ) ) return 0 ; if ( dp [ i ] [ sum ] != -1 ) return dp [ i ] [ sum ] ; int ans = 0 ; if ( ( sum + find_max ( i + 1 , sum , v , k ) ) % k == 0 ) ans = find_max ( i + 1 , sum , v , k ) ; if ( ( sum + v [ i ] + find_max ( i + 1 , ( sum + v [ i ] ) % k , v , k ) ) % k == 0 ) ans = max ( ans , v [ i ] + find_max ( i + 1 , ( sum + v [ i ] ) % k , v , k ) ) ; return dp [ i ] [ sum ] = ans ; } int main ( ) { vector < int > arr = { 43 , 1 , 17 , 26 , 15 } ; int k = 16 ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << find_max ( 0 , 0 , arr , k ) ; }