Tìm tổng tích lớn nhất của hai mảng trong C++

Trong bài toán này, chúng ta được cung cấp hai mảng arr1[] và arr2[] kích thước n. Nhiệm vụ là viết chương trình tìm tổng tích lớn nhất của hai mảng.

Mô tả bài toán

Chúng ta cần tìm tổng lớn nhất của tích các cặp phần tử, mỗi cặp gồm một phần tử từ arr1 và một phần tử từ arr2.

Ví dụ minh họa

Đầu vào

arr1[] = {3, 5, 6}
arr2[] = {1, 4, 2}

Đầu ra

37

Giải thích

Tổng tích lớn nhất: 6*4 + 5*2 + 3*1 = 24 + 10 + 3 = 37

Phương pháp giải

Cách đơn giản là tìm tất cả các cặp phần tử từ hai mảng và trả về tổng lớn nhất.

Cách hiệu quả hơn: nhân các giá trị lớn nhất từ cả hai mảng với nhau. Cách dễ dàng để làm điều này là sắp xếp cả hai mảng theo thứ tự giảm dần. Sau đó nhân các phần tử cùng chỉ số từ 0 đến n-1 và trả về tổng của chúng.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;

int calcMaxSumOfProd(int arr1[], int arr2[], int n) {
    int maxSum = 0;
    sort(arr1, arr1 + n, greater<int>());
    sort(arr2, arr2 + n, greater<int>());
    for (int i = 0; i < n; i++)
        maxSum += (arr1[i] * arr2[i]);
    return maxSum;
}

int main() {
    int arr1[] = { 3, 5, 6 };
    int arr2[] = { 1, 4, 2 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Tổng tích lớn nhất của hai mảng là " << calcMaxSumOfProd(arr1, arr2, n);
    return 0;
}

Đầu ra

Tổng tích lớn nhất của hai mảng là 37