Number of pairs with maximum sum
Given an array arr[], count number of pairs arr[i], arr[j] such that arr[i] + arr[j] is maximum and i < j.
Example: Input : arr[] = {1, 1, 1, 2, 2, 2} Output : 3 Explanation: The maximum possible pair sum where i<j is 4, which is given by 3 pairs, so the answer is 3 the pairs are (2, 2), (2, 2) and (2, 2) Input : arr[] = {1, 4, 3, 3, 5, 1} Output : 1 Explanation: The pair 4, 5 yields the maximum sum i.e, 9 which is given by 1 pair only
Method 1 (Naive)
Traverse a loop i from 0 to n, i.e length of the array and another loop j from i+1 to n to find all possible pairs with i<j. Find the pair with the maximum possible sum, again traverse for all pairs and keep the count of the number of pairs which gives the pair sum equal to maximum
 C++

// 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;
}
Output:
3
Time complexity:O(n^2)
Method 2 (Efficient)
If we take a closer look, we can notice following facts.
 Maximum element is always part of solution
 If maximum element appears more than once, then result is maxCount * (maxCount – 1)/2. We basically need to choose 2 elements from maxCount (^{maxCount}C_{2}).
 If maximum element appears once, then result is equal to count of second maximum element. We can form a pair with every second max and max

// 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)
{
// Find maximum and second maximum elements.
// Also find their counts.
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 maximum element appears more than once.
if
(maxCount > 1)
return
maxCount * (maxCount  1) / 2;
// If maximum element appears only once.
return
secondMaxCount;
}
// driver program to test the above function
int
main()
{
int
array[] = { 1, 1, 1, 2, 2, 2, 3 };
int
n =
sizeof
(array) /
sizeof
(array[0]);
cout << sum(array, n);
return
0;
}
Output:
3
Time complexity:O(n)
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/numberpairsmaximumsum/
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide