Maximum sum of elements divisible by K from the given array |
k = 16 NEW_LINE arr = [ 43 , 1 , 17 , 26 , 15 ] NEW_LINE n = len ( arr ) NEW_LINE dp = [ [ 0 for i in range ( k ) ] for j in range ( n + 2 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( k ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT dp [ i ] [ arr [ i - 1 ] % k ] = max ( dp [ i ] [ arr [ i - 1 ] % k ] , arr [ i - 1 ] ) NEW_LINE for j in range ( k ) : NEW_LINE INDENT m = ( j + arr [ i - 1 ] ) % k NEW_LINE if dp [ i - 1 ] [ j ] != 0 : NEW_LINE INDENT dp [ i ] [ m ] = max ( dp [ i ] [ m ] , arr [ i - 1 ] + dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT print ( dp [ n ] [ 0 ] ) NEW_LINE