Tìm cặp phần tử có tích lớn nhất trong mảng số nguyên C++

Cho một mảng A chứa n phần tử (có thể dương hoặc âm). Cần tìm cặp (x, y) sao cho tích x*y là lớn nhất. Ví dụ với A = [-1, -4, -3, 0, 2, -5], cặp cho tích lớn nhất là (-4, -5) với tích bằng 20.

Giải thuật

Theo dõi 4 giá trị: hai số dương lớn nhất (positive_max, positive_second_max) và hai số âm có giá trị tuyệt đối lớn nhất (negative_max, negative_second_max). So sánh tích của hai cặp này để chọn kết quả.

Ví dụ minh họa

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

void maxProdPair(int arr[], int n) {
    if (n < 2) {
        cout << "Khong co cap phan tu";
        return;
    }
    if (n == 2) {
        cout << "(" << arr[0] << ", " << arr[1] << ")" << endl;
        return;
    }
    int pos_max = INT_MIN, pos_second_max = INT_MIN;
    int neg_max = INT_MIN, neg_second_max = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] > pos_max) {
            pos_second_max = pos_max;
            pos_max = arr[i];
        } else if (arr[i] > pos_second_max)
            pos_second_max = arr[i];
        
        if (arr[i] < 0 && abs(arr[i]) > abs(neg_max)) {
            neg_second_max = neg_max;
            neg_max = arr[i];
        } else if (arr[i] < 0 && abs(arr[i]) > abs(neg_second_max))
            neg_second_max = arr[i];
    }
    
    if (neg_max * neg_second_max > pos_max * pos_second_max)
        cout << "(" << neg_max << ", " << neg_second_max << ")" << endl;
    else
        cout << "(" << pos_max << ", " << pos_second_max << ")" << endl;
}

int main() {
    int arr[] = {-1, -4, -3, 0, 2, -5};
    int n = sizeof(arr)/sizeof(arr[0]);
    maxProdPair(arr, n);
}

Kết quả

(-5, -4)