Dada una array arr[], cuente el número de pares arr[i], arr[j] tales que arr[i] + arr[j] es máximo e i < j.
Example :
Input : arr[] = {1, 1, 1, 2, 2, 2}
Output : 3
Explanation: The maximum possible pair
sum where i
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
Java
// Java program to count pairs
// with maximum sum.
class GFG {
// function to find the number of
// maximum pair sums
static int sum(int a[], int n)
{
// traverse through all the pairs
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
maxSum = Math.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
public static void main(String[] args)
{
int array[] = { 1, 1, 1, 2, 2, 2 };
int n = array.length;
System.out.println(sum(array, n));
}
}
// This code is contributed by Prerna Saini
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 (maxCountC2).
- 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
Java
// Java program to count pairs
// with maximum sum.
import java.io.*;
class GFG {
// function to find the number
// of maximum pair sums
static int sum(int a[], int n)
{
// Find maximum and second maximum
// elements. Also find their counts.
int maxVal = a[0], maxCount = 1;
int secondMax = Integer.MIN_VALUE,
secondMaxCount = 0;
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
public static void main(String[] args)
{
int array[] = { 1, 1, 1, 2, 2, 2, 3 };
int n = array.length;
System.out.println(sum(array, n));
}
}
// This code is contributed by Prerna Saini
Output :
3
Time complexity:O(n)
Please refer complete article on Number of pairs with maximum sum for more details!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA