Maximum sum of elements divisible by K from the given array | Python3 implementation ; 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
dp = [ [ - 1 for i in range ( 1001 ) ] for j in range ( 1001 ) ] NEW_LINE def find_max ( i , sum , v , k ) : NEW_LINE INDENT if ( i == len ( v ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ sum ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ sum ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( ( sum + find_max ( i + 1 , sum , v , k ) ) % k == 0 ) : NEW_LINE INDENT ans = find_max ( i + 1 , sum , v , k ) NEW_LINE DEDENT if ( ( sum + v [ i ] + find_max ( i + 1 , ( sum + v [ i ] ) % k , v , k ) ) % k == 0 ) : NEW_LINE INDENT ans = max ( ans , v [ i ] + find_max ( i + 1 , ( sum + v [ i ] ) % k , v , k ) ) NEW_LINE DEDENT dp [ i ] [ sum ] = ans NEW_LINE return dp [ i ] [ sum ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 43 , 1 , 17 , 26 , 15 ] NEW_LINE k = 16 NEW_LINE print ( find_max ( 0 , 0 , arr , k ) ) NEW_LINE DEDENT