Số cặp tối đa tạo ra cùng tổng trong C++

Chúng ta được cho một mảng số nguyên. Mục tiêu là tìm số cặp tối đa trong mảng mà khi cộng lại tạo ra cùng một tổng. Chúng ta phải tìm số lượng tối đa của các cặp như vậy.

Ví dụ

Đầu vào

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

Đầu ra

Số cặp tối đa cùng tổng: 3

Giải thích − Tổng các cặp số:

{1,2}, {1,2} Tổng: 3
{1,3}, {2,2} Tổng: 4
{1,4}, {2,3}, {3,2} Tổng: 5
{2,4} Tổng: 6
{3,4} Tổng: 7
Số cặp tối đa cùng tổng là 3 (cho tổng = 5)

Đầu vào

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

Đầu ra

Số cặp tối đa cùng tổng: 1

Giải thích − Tổng các cặp:

{5,3} Tổng: 8
{5,6} Tổng: 11
{5,1} Tổng: 6
{3,6} Tổng: 9
{3,1} Tổng: 4
{6,1} Tổng: 7
Số cặp tối đa cùng tổng là 1.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số.
• Số nguyên 'size' lưu độ dài mảng.
• Hàm countEqualSum(int arr[], int n) nhận mảng, kích thước, trả về số cặp tối đa tạo ra cùng tổng.
• Đầu tiên lấy mảng 'sum' lưu tần suất các tổng duy nhất.
• Tại mỗi chỉ số của sum, tăng count của phần tử đó.
• Mỗi chỉ số của mảng sum là tổng của một cặp phần tử.
• Tìm count tối đa bằng cách tìm max trong mảng sum lưu vào maxC.
• Trả về maxC làm kết quả.

Ví dụ mã nguồn

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

// Hàm trả về số cặp tối đa với tổng bằng nhau
int countEqualSum(int arr[], int n) { 
    int sum[20] = {0}; 
    int maxC = 0; 
    // Lưu count tổng của tất cả cặp
    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 << "Số cặp tối đa tạo ra cùng tổng: " 
         << countEqualSum(Arr, size); 
    return 0; 
}

Kết quả

Số cặp tối đa tạo ra cùng tổng: 3