在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