นับวิธีเลือกคู่ที่มีความต่างมากที่สุด ใน C++

ได้รับอาร์เรย์ Arr[] ต้องการนับจำนวนคู่ (i≠j) ที่ความต่าง |arr[i]-arr[j]| เท่ากับความต่างสูงสุดของคู่ใดๆ

ข้อสังเกต

ความต่างมากที่สุด = max(arr) - min(arr)

นับคู่ที่เป็น (min, max) หรือ (max, min)

ตัวอย่าง

อินพุต: arr[] = {1, 2, 3, 2, 4, 1, 5}

เอาต์พุต: 2 (คู่ (1,5) มี 2 วิธี)

อินพุต: arr[] = {2, 4, 2, 4}

เอาต์พุต: 4 (min=2 มี 2 ตัว, max=4 มี 2 ตัว → 2×2=4 คู่)

แนวทาง

• หา min และ max ของอาร์เรย์
• maxdiff = max - min
• ลูปซ้อน 2 ชั้นนับคู่ที่ความต่าง = maxdiff (นับทั้ง arr[i]-arr[j] และ arr[j]-arr[i])

ตัวอย่างโค้ด C++

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

int countWays(int arr[], int n) {
    int count = 0, diff, maxdiff = 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];
    }
    maxdiff = maxx - mini;
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            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 << endl << "No. of ways of choosing pair with maximum difference: " << countWays(Arr, N);
    return 0;
}

ผลลัพธ์

No. of ways of choosing pair with maximum difference: 4