Đếm số cách chọn cặp có hiệu lớn nhất trong mảng C++

Cho mảng Arr[]. Đếm số cặp (i,j) với i≠j có hiệu bằng hiệu lớn nhất có thể (max - min).

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1, 2, 3, 2, 4, 1, 5}
• Output: 2
• Giải thích: Min=1, Max=5, MaxDiff=4. Cặp (1,5) xuất hiện 2 lần (2 số 1 × 1 số 5).

Ví dụ 2:

• Input: arr = {2, 4, 2, 4}
• Output: 4
• Giải thích: Min=2 (2 lần), Max=4 (2 lần). Cặp có thứ tự: 2×2×2 = 4? Thực tế: (2,4) và (4,2) mỗi cặp giá trị xuất hiện 2×2=4 lần.

Quan sát quan trọng

Hiệu lớn nhất luôn là max_val - min_val. Số cặp = freq[min] × freq[max] × 2 (nếu min≠max, tính cặp có thứ tự).

Mã nguồn C++ (Vét cạn O(n²))

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

int countWays(int arr[], int n) {
    int count = 0;
    int mini = arr[0], maxx = arr[0];
    for (int i = 0; i < n; i++) {
        if (arr[i] < mini) mini = arr[i];
        if (arr[i] > maxx) maxx = arr[i];
    }
    int maxdiff = maxx - mini;
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = arr[i] - arr[j];
            if (diff == maxdiff) count++;
            diff = arr[j] - arr[i];
            if (diff == maxdiff) count++;
        }
    }
    return count;
}

int main() {
    int Arr[] = {3, 2, 1, 1, 3};
    int N = 5;
    cout << "So cach chon cap hieu lon nhat: " << countWays(Arr, N);
    return 0;
}

Kết quả chạy chương trình

So cach chon cap hieu lon nhat: 4

Tối ưu hóa O(n) - Đếm tần suất

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

long long countWaysOptimized(int arr[], int n) {
    int mini = *min_element(arr, arr + n);
    int maxx = *max_element(arr, arr + n);
    
    if (mini == maxx) {
        // Tất cả phần tử bằng nhau, hiệu = 0
        return 1LL * n * (n - 1); // Cặp có thứ tự
    }
    
    long long cntMin = 0, cntMax = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == mini) cntMin++;
        if (arr[i] == maxx) cntMax++;
    }
    return cntMin * cntMax * 2; // (min,max) và (max,min)
}

Độ phức tạp