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

Cho mảng số nguyên (có thể âm). Ghép các phần tử thành cặp, nhân hai số trong mỗi cặp, tìm tổng lớn nhất. Phần tử lẻ (nếu có) cộng trực tiếp.

Thuật toán

• Sắp xếp mảng tăng dần.
• Ghép các số âm từ đầu: nếu cả hai ≤ 0 thì nhân (dương), cộng vào sum.
• Ghép các số dương từ cuối: nếu cả hai > 0 thì nhân, cộng vào sum.
• Nếu còn lại 1 số âm và 1 số dương: nhân chúng.
• Nếu còn 1 phần tử đơn lẻ: cộng trực tiếp.
• Lấy modulo 1e9+7.

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

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

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

int main() {
    int arr[] = {-1, 9, 4, 5, -4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSum(arr, n);
    return 0;
}

Đầu ra

87