Find Maximum dot product of two arrays with insertion of 0 's | Function compute Maximum Dot Product and return it ; Create 2D Matrix that stores dot product dp [ i + 1 ] [ j + 1 ] stores product considering B [ 0. . i ] and A [ 0. . . j ] . Note that since all m > n , we fill values in upper diagonal of dp [ ] [ ] ; Traverse through all elements of B [ ] ; Consider all values of A [ ] with indexes greater than or equal to i and compute dp [ i ] [ j ] ; Two cases arise 1 ) Include A [ j ] 2 ) Exclude A [ j ] ( insert 0 in B [ ] ) ; return Maximum Dot Product ; Driver Code
def MaxDotProduct ( A , B , m , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT for j in range ( i , m + 1 , 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( ( dp [ i - 1 ] [ j - 1 ] + ( A [ j - 1 ] * B [ i - 1 ] ) ) , dp [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT return dp [ n ] [ m ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 2 , 3 , 1 , 7 , 8 ] NEW_LINE B = [ 3 , 6 , 7 ] NEW_LINE m = len ( A ) NEW_LINE n = len ( B ) NEW_LINE print ( MaxDotProduct ( A , B , m , n ) ) NEW_LINE DEDENT