算法设计（查找插入0的两个数组的最大点积）

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
Java
Python3
C#

【算法设计（查找插入0的两个数组的最大点积）】给定两个大小为m和n的正整数数组, 其中m> n。我们需要通过在第二个数组中插入零来最大化点积, 但是我们不能打扰元素的顺序。
例子：

Input : A[] = {2, 3 , 1, 7, 8} B[] = {3, 6, 7}Output : 107Explanation : We get maximum dot product afterinserting 0 at first and third positions in second array.Maximum Dot Product : = A[i] * B[j] 2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 107Input : A[] = {1, 2, 3, 6, 1, 4}B[] = {4, 5, 1}Output : 46

询问：Directi面试
推荐：请在"实践首先, 在继续解决方案之前。
解决此问题的另一种方法是, 对于每对元素a [i]和B [j], 其中j> = i, 我们有两种选择：

我们将A [i]和B [j]相乘并加到乘积上(我们包括A [i])。
我们从乘积中排除A [i](换句话说, 我们在B []的当前位置插入0)

这个想法是使用动态编程.

1) Given Array A[] of size 'm' and B[] of size 'n'2) Create 2D matrix 'DP[n + 1][m + 1]' initialize itwith '0'3) Run loop outer loop for i = 1 to nInner loop j = i to m// Two cases arise// 1) Include A[j]// 2) Exclude A[j] (insert 0 in B[])dp[i][j]= max(dp[i-1][j-1] + A[j-1] * B[i -1], dp[i][j-1]) // Last return maximum dot product that is return dp[n][m]

以下是上述想法的实现。
C ++

// C++ program to find maximum dot product of two array #include< bits/stdc++.h> using namespace std; // Function compute Maximum Dot Product and // return it long long int MaxDotProduct( int A[], int B[], int m, int n) { // 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[][] long long int dp[n+1][m+1]; memset (dp, 0, sizeof (dp)); // Traverse through all elements of B[] for ( int i=1; i< =n; i++)// Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for ( int j=i; j< =m; j++)// Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = max((dp[i-1][j-1] + (A[j-1]*B[i-1])) , dp[i][j-1]); // return Maximum Dot Product return dp[n][m] ; }// Driver program to test above function int main() { int A[] = { 2, 3 , 1, 7, 8 } ; int B[] = { 3, 6, 7 } ; int m = sizeof (A)/ sizeof (A[0]); int n = sizeof (B)/ sizeof (B[0]); cout < < MaxDotProduct(A, B, m, n); return 0; }

Java

// Java program to find maximum // dot product of two array import java.util.*; class GFG { // Function to compute Maximum // Dot Product and return it static int MaxDotProduct( int A[], int B[], int m, int n) { // 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[][] int dp[][] = new int [n + 1 ][m + 1 ]; for ( int [] row : dp) Arrays.fill(row, 0 ); // Traverse through all elements of B[] for ( int i = 1 ; i < = n; i++)// Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for ( int j = i; j < = m; j++)// Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = Math.max((dp[i - 1 ][j - 1 ] + (A[j - 1 ] * B[i - 1 ])), dp[i][j - 1 ]); // return Maximum Dot Product return dp[n][m]; }// Driver code public static void main(String[] args) { int A[] = { 2 , 3 , 1 , 7 , 8 }; int B[] = { 3 , 6 , 7 }; int m = A.length; int n = B.length; System.out.print(MaxDotProduct(A, B, m, n)); } }// This code is contributed by Anant Agarwal.

Python3

# Python 3 program to find maximum dot # product of two array# Function compute Maximum Dot Product # and return it def MaxDotProduct(A, B, m, n):# 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[][] dp = [[ 0 for i in range (m + 1 )] for j in range (n + 1 )]# Traverse through all elements of B[] for i in range ( 1 , n + 1 , 1 ):# Consider all values of A[] with indexes # greater than or equal to i and compute # dp[i][j] for j in range (i, m + 1 , 1 ):# Two cases arise # 1) Include A[j] # 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = max ((dp[i - 1 ][j - 1 ] + (A[j - 1 ] * B[i - 1 ])) , dp[i][j - 1 ])# return Maximum Dot Product return dp[n][m] # Driver Code if __name__ = = '__main__' : A = [ 2 , 3 , 1 , 7 , 8 ] B = [ 3 , 6 , 7 ] m = len (A) n = len (B) print (MaxDotProduct(A, B, m, n))# This code is contributed by # Sanjit_Prasad

// C# program to find maximum // dot product of two array using System; public class GFG{// Function to compute Maximum // Dot Product and return it static int MaxDotProduct( int []A, int []B, int m, int n) { // 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[][] int [, ]dp = new int [n + 1, m + 1]; // Traverse through all elements of B[] for ( int i = 1; i < = n; i++)// Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for ( int j = i; j < = m; j++)// Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i, j] = Math.Max((dp[i - 1, j - 1] + (A[j - 1] * B[i - 1])), dp[i, j - 1]); // return Maximum Dot Product return dp[n, m]; }// Driver code public static void Main() { int []A = {2, 3, 1, 7, 8}; int []B = {3, 6, 7}; int m = A.Length; int n = B.Length; Console.Write(MaxDotProduct(A, B, m, n)); } }/*This code is contributed by 29AjayKumar*/

输出如下：