C++程序 计算最大总和的对数

给定一个数组arr[]，计算出满足 arr[i] + arr[j] 最大且 i < j 的所有数对 (arr[i], arr[j]) 的数量。

示例 ：
输入：arr [] = {1, 1, 1, 2, 2, 2}
输出：3

方法1（Naive）

通过一个循环 i 从 0 到 n（也就是数组长度），再通过另外一个循环 j 从 i+1 到 n，来查找所有可能的数对 (i, j)。

// CPP program to count pairs with maximum sum. 

#include <bits/stdc++.h> 

using namespace std; 

  

// function to find the number of maximum pair sums 

int sum(int a[], int n) 

{ 

    // traverse through all the pairs 

    int maxSum = INT_MIN; 

    for (int i = 0; i < n; i++) 

        for (int j = i + 1; j < n; j++) 

            maxSum = max(maxSum, a[i] + a[j]); 

  

    // traverse through all pairs and keep a count 

    // of the number of maximum pairs 

    int c = 0; 

    for (int i = 0; i < n; i++) 

        for (int j = i + 1; j < n; j++) 

            if (a[i] + a[j] == maxSum) 

                c++; 

    return c; 

} 

  

// driver program to test the above function 

int main() 

{ 

    int array[] = { 1, 1, 1, 2, 2, 2 }; 

    int n = sizeof(array) / sizeof(array[0]); 

    cout << sum(array, n); 

    return 0; 

} 

输出:

3

时间复杂度： O(n^2)

方法2（Efficient）

如果我们仔细观察，我们可以注意以下几点。

1. 最大元素总是解决方案的一部分
2. 如果最大元素出现不止一次，则结果为maxCount *（maxCount-1）/ 2。 我们基本上需要从maxCount（ maxCount C 2 ）中选择2个元素。
3. 如果最大元素只出现一次，则结果等于第二大元素的计数。 我们可以将每个第二大和最大值配对形成一对。

// CPP程序用于计算最大和对的数量。
#include <bits/stdc++.h>
using namespace std;
  
// 查找最大对和的数量的函数
int sum(int a[], int n)
{
    // 查找最大和第二大的元素，以及它们的出现次数。
    int maxVal = a[0], maxCount = 1;
    int secondMax = INT_MIN, secondMaxCount;
    for (int i = 1; i < n; i++) {
        if (a[i] == maxVal)
            maxCount++;
        else if (a[i] > maxVal) {
            secondMax = maxVal;
            secondMaxCount = maxCount;
            maxVal = a[i];
            maxCount = 1;
        }
        else if (a[i] == secondMax) {
            secondMax = a[i];
            secondMaxCount++;
        }
        else if (a[i] > secondMax) {
            secondMax = a[i];
            secondMaxCount = 1;
        }
    }
  
    // 如果最大元素重复出现。
    if (maxCount > 1)
        return maxCount * (maxCount - 1) / 2;
  
    // 如果最大元素只出现一次。
    return secondMaxCount;
}
  
// 驱动程序来测试上面的函数
int main()
{
    int array[] = { 1, 1, 1, 2, 2, 2, 3 };
    int n = sizeof(array) / sizeof(array[0]);
    cout << sum(array, n);
    return 0;
}  

输出结果:

3

时间复杂度: O(n)