在C ++中查找插入0的两个数组的最大点积

假设我们有两个大小为m和n的正整数数组。m> n。我们必须通过在第二个数组中插入零来最大化点积。我们必须记住的一件事是，我们将不会更改给定数组中元素的顺序。假设数组为A = [2，3，1，7，8]，另一个数组B = [3，6，7]。输出为107。在第二个数组的第一个和第三个位置插入0后，我们可以最大化点积。因此乘积将为2 * 0 + 3 * 3 +1 * 0 + 7 * 6 + 8 * 7 = 107。

为了解决这个问题，我们将使用动态编程方法。因此，A的大小为m，B的大小为n。我们将为动态编程顺序（n + 1）x（m + 1）创建一个表，并用0填充它。现在使用这些步骤来完成其余工作-

• 对于范围1至n的i：

• 对于j：= i至m

• 对于j：= i至m

• table [i，j]：= max（table [i-1，j-1] + A [j-1] * B [i-1]，table [i，j-1]）

示例

#include <iostream>
using namespace std;
long long int findMaximumDotProd(int A[], int B[], int m, int n) {
   long long int table[n+1][m+1];
   for(int i = 0; i<=n; i++){
      for(int j = 0; j<=m; j++){
         table[i][j] = 0;
      }
   }
   for (int i=1; i<=n; i++)
   for (int j=i; j<=m; j++)
   table[i][j] = max((table[i-1][j-1] + (A[j-1]*B[i-1])) , table[i][j-1]);
   return table[n][m] ;
}
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 << "Maximum dot product: " << findMaximumDotProd(A, B, m, n);
}

输出结果

Maximum dot product: 107