Number of Pairs with Maximum Sum

Summary

Given an array of integers, find the number of pairs that have a maximum sum. This problem involves arrays and data structures.

Detailed Explanation

The problem can be solved by iterating over the array and keeping track of the maximum pair sum encountered so far. Initialize two variables, maxSum to store the maximum sum found, and count to count the number of pairs with this sum.

Here is a step-by-step breakdown:

Iterate over the array.
For each element, calculate the sum with all other elements in the array (this can be done using two nested loops).
Keep track of the maximum sum found so far (maxSum) and count the number of pairs that have this sum (count).
After iterating over the entire array, return count.

Time complexity: O(n^2) due to the nested loops. Space complexity: O(1), as only a constant amount of space is used.

Here's an ASCII art diagram to illustrate the process:

  +---------------+
  |       Array    |
  +---------------+
           |
           |
      Iterate over
           |
           v
  +---------------+
  |  Calculate sum  |
  |  with each element|
  +---------------+
           |
           |
      Keep track of maxSum and count
           |
           v
  +---------------+
  |   Return count   |
  +---------------+

Optimized Solutions

Java

public int solution(int[] arr) { int n = arr.length; int maxSum = Integer.MIN_VALUE; int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sum = arr[i] + arr[j]; if (sum > maxSum) { maxSum = sum; count = 1; } else if (sum == maxSum) { count++; } } } return count; }