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

Cho hai mảng cùng kích thước. Tìm tổng lớn nhất bằng cách nhân từng cặp phần tử (mỗi phần tử dùng đúng 1 lần).

Theo bất đẳng thức sắp xếp: tổng tích lớn nhất khi sắp xếp cả hai mảng cùng chiều (cùng tăng hoặc cùng giảm).

Thuật toán

• Sắp xếp cả hai mảng tăng dần.
• Tính tổng a[i] * b[i].

Ví dụ triển khai (C++)

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

int maximumSOP(int *a, int *b, int n) {
    sort(a, a + n);
    sort(b, b + n);
    int sop = 0;
    for (int i = 0; i < n; i++) sop += a[i] * b[i];
    return sop;
}

int main() {
    int A[] = {1, 2, 3};
    int B[] = {4, 5, 1};
    int n = sizeof(A) / sizeof(A[0]);
    cout << maximumSOP(A, B, n);
    return 0;
}

Đầu ra

24