দুটি ধনাত্মক পূর্ণসংখ্যার অ্যারে A (আকার m) এবং B (আকার n) দেওয়া আছে, যেখানে m > n। B-তে ০ যোগ করে (কম করে) ডট প্রোডাক্ট সর্বোচ্চ করতে হবে, কিন্তু উপাদানগুলোর ক্রম বদলানো যাবে না। উদাহরণস্বরূপ, A = [2, 3, 1, 7, 8], B = [3, 6, 7] হলে আউটপুট ১০৭। B-র প্রথম ও তৃতীয় অবস্থানে ০ যোগ করলে: 2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 107।
DP টেবিলের আকার (n+1) x (m+1)। টেবিল ০ দিয়ে ভরা থাকে।
- i = 1 থেকে n পর্যন্ত লুপ।
- 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
