C++で0を挿入した2つの配列の最大内積を求めます

サイズmとnの正の整数の2つの配列があるとします。 m>n。 2番目の配列にゼロを挿入して、内積を最大化する必要があります。指定された配列内の要素の順序は変更しないことに注意する必要があります。配列がA=[2、3、1、7、8]であり、別の配列B =[3、6、7]であるとします。出力は107になります。2番目の配列の1番目と3番目の位置に0を挿入した後、内積を最大化できます。したがって、積は2 * 0 + 3 * 3 + 1 * 0 + 7 * 6 + 8 * 7=107になります。

これを解決するために、動的計画法のアプローチを使用します。したがって、Aのサイズはmであり、Bのサイズはnです。次数（n + 1）x（m + 1）の動的計画法用のテーブルを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