# 2815. Max Pair Sum in an Array

## Description

You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.

Return the maximum sum or -1 if no such pair exists.

Example 1:

Input: nums = [51,71,17,24,42]
Output: 88
Explanation:
For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88.
For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66.
It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.

Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists in nums with equal maximum digits.


Constraints:

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

## Solutions

Solution 1: Enumeration

First, we initialize the answer variable $ans=-1$. Next, we directly enumerate all pairs $(nums[i], nums[j])$ where $i \lt j$, and calculate their sum $v=nums[i] + nums[j]$. If $v$ is greater than $ans$ and the largest digit of $nums[i]$ and $nums[j]$ are the same, then we update $ans$ with $v$.

The time complexity is $O(n^2 \times \log M)$, where $n$ is the length of the array and $M$ is the maximum value in the array.

• class Solution {
public int maxSum(int[] nums) {
int ans = -1;
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int v = nums[i] + nums[j];
if (ans < v && f(nums[i]) == f(nums[j])) {
ans = v;
}
}
}
return ans;
}

private int f(int x) {
int y = 0;
for (; x > 0; x /= 10) {
y = Math.max(y, x % 10);
}
return y;
}
}

• class Solution {
public:
int maxSum(vector<int>& nums) {
int ans = -1;
int n = nums.size();
auto f = [](int x) {
int y = 0;
for (; x; x /= 10) {
y = max(y, x % 10);
}
return y;
};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int v = nums[i] + nums[j];
if (ans < v && f(nums[i]) == f(nums[j])) {
ans = v;
}
}
}
return ans;
}
};

• class Solution:
def maxSum(self, nums: List[int]) -> int:
ans = -1
for i, x in enumerate(nums):
for y in nums[i + 1 :]:
v = x + y
if ans < v and max(str(x)) == max(str(y)):
ans = v
return ans


• func maxSum(nums []int) int {
ans := -1
f := func(x int) int {
y := 0
for ; x > 0; x /= 10 {
y = max(y, x%10)
}
return y
}
for i, x := range nums {
for _, y := range nums[i+1:] {
if v := x + y; ans < v && f(x) == f(y) {
ans = v
}
}
}
return ans
}

• function maxSum(nums: number[]): number {
const n = nums.length;
let ans = -1;
const f = (x: number): number => {
let y = 0;
for (; x > 0; x = Math.floor(x / 10)) {
y = Math.max(y, x % 10);
}
return y;
};
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
const v = nums[i] + nums[j];
if (ans < v && f(nums[i]) === f(nums[j])) {
ans = v;
}
}
}
return ans;
}