จำนวนคู่อาเรย์สูงสุดที่ให้ผลรวมเท่ากันใน C++

เราได้รับอาเรย์จำนวนเต็ม เป้าหมายคือหาจำนวนคู่สูงสุดในอาเรย์ที่บวกกันได้ผลรวมเท่ากัน

อินพุต

Arr[] = {1, 2, 3, 4, 2}

เอาต์พุต

Maximum count of pairs with same sum: 3

คำอธิบาย − ผลรวมคู่: {1,2},{1,2}=3; {1,3},{2,2}=4; {1,4},{2,3},{3,2}=5 (มากที่สุด 3 คู่); {2,4}=6; {3,4}=7

อินพุต

Arr[] = {5, 3, 6, 1}

เอาต์พุต

Maximum count of pairs with same sum: 1

คำอธิบาย − ทุกคู่ให้ผลรวมต่างกัน มากที่สุด 1 คู่

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• อาเรย์ Arr[] และ size
• ฟังก์ชัน countEqualSum(int arr[], int n) คืนค่าจำนวนคู่สูงสุดที่ผลรวมเท่ากัน
• อาเรย์ sum[20] เก็บความถี่ผลรวม (สมมติผลรวมไม่เกิน 20)
• ลูป i=0..n-2, j=i+1..n-1 sum[arr[i]+arr[j]]++
• หาค่าสูงสุดใน sum[] เก็บใน maxC
• คืนค่า maxC

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

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

int countEqualSum(int arr[], int n) {
    int sum[20] = {0};
    int maxC = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            sum[arr[i] + arr[j]]++;
    for (int i = 0; i < 20; i++)
        if (sum[i] > maxC)
            maxC = sum[i];
    return maxC;
}

int main() {
    int Arr[] = {1, 2, 3, 4, 2};
    int size = 5;
    cout << "Maximum count of pairs which generate the same sum: " << countEqualSum(Arr, size);
    return 0;
}

ผลลัพธ์

Maximum count of pairs which generate the same sum: 3