Tìm tổng tích cặp lớn nhất trong mảng cho phép số âm bằng C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] chứa n giá trị nguyên (cho phép số âm). Nhiệm vụ là viết chương trình tìm tổng tích cặp lớn nhất trong mảng cho phép số âm.

Mô tả bài toán

Chúng ta cần tạo các cặp từ các phần tử của mảng sao cho tổng của tích các phần tử trong các cặp là lớn nhất.

Ví dụ minh họa

Đầu vào

arr[] = {-5, 2, 3, 7, -1, 1, -3, 12}

Đầu ra

104

Giải thích

Các cặp được xem xét: (-5, -3), (2, 3), (-1, 1), (7, 12)
Tổng tích = (-5 * -3) + (2 * 3) + (-1 * 1) + (7 * 12) = 15 + 6 - 1 + 84 = 104.

Phương pháp giải

Để giải bài toán, chúng ta sẽ tìm các cặp sao cho tổng tích của chúng là lớn nhất. Để tối đa hóa tổng, chúng ta cần ghép các giá trị cùng dấu với nhau. Để việc ghép cặp dễ dàng hơn, ta sắp xếp mảng sau đó ghép các số âm với nhau và các số dương với nhau. Sau đó kiểm tra xem còn lại một số dương, một số âm, hoặc cả hai. Nếu còn một số dương/âm thì cộng vào tổng, nếu còn một dương và một âm thì cộng tích của chúng.

Thuật toán

Khởi tạo

maxSum = 0.

Bước 1

Sắp xếp mảng arr[].

Bước 2

Duyệt qua tất cả các giá trị âm của mảng. Tạo cặp và cộng tích vào maxSum.

Bước 3

Duyệt qua tất cả các giá trị dương của mảng. Tạo cặp và cộng tích vào maxSum.

Bước 4

Kiểm tra các giá trị còn lại.

Bước 4.1

Nếu còn một giá trị dương, cộng vào maxSum.

Bước 4.2

Nếu còn một giá trị âm, cộng vào maxSum.

Bước 4.3

Nếu còn một giá trị dương và một giá trị âm, cộng tích của chúng vào maxSum.

Bước 5

Trả về maxSum.

Chương trình minh họa

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

long calcSumPairProd(int arr[], int n) {
    long maxSum = 0;
    sort(arr, arr + n);
    int i = 0, j = (n - 1);
    
    while (i < n && arr[i] < 0) {
        if (i != n - 1 && arr[i + 1] <= 0) {
            maxSum = (maxSum + (arr[i] * arr[i + 1]));
            i += 2;
        } else
            break;
    }
    
    while (j >= 0 && arr[j] > 0) {
        if (j != 0 && arr[j - 1] > 0) {
            maxSum = (maxSum + (arr[j] * arr[j - 1]));
            j -= 2;
        } else
            break;
    }
    
    if (j > i)
        maxSum = (maxSum + (arr[i] * arr[j]));
    else if (i == j)
        maxSum = (maxSum + arr[i]);
    
    return maxSum;
}

int main() {
    int arr[] = { -5, 2, 3, 7, -1, 1, -3, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tổng tích cặp lớn nhất trong mảng là " << calcSumPairProd(arr, n);
    return 0;
}

Đầu ra

Tổng tích cặp lớn nhất trong mảng là 104