หาผลคูณสเกลาร์สูงสุดของสองอาร์เรย์โดยแทรกศูนย์ใน C++

ปัญหา

กำหนดอาร์เรย์สองตัว A (ขนาด m) และ B (ขนาด n) โดย m > n จงเพิ่มผลคูณสเกลาร์ (dot product) ให้สูงสุดโดยการแทรก 0 ลงในอาร์เรย์ B โดยไม่เปลี่ยนลำดับของสมาชิกในอาร์เรย์ทั้งสอง

ตัวอย่าง: A = [2, 3, 1, 7, 8], B = [3, 6, 7] ผลลัพธ์คือ 107 โดยแทรก 0 ที่ตำแหน่ง 1 และ 3 ของ B: 2×0 + 3×3 + 1×0 + 7×6 + 8×7 = 107

วิธี Dynamic Programming

สร้างตาราง DP ขนาด (n+1) × (m+1) เติมค่า 0 แล้วคำนวณตามสูตร:

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