minimize-maximum-pair-sum-in-array

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Would sorting help find the optimal order?

Given a specific element, how would you minimize its specific pairwise sum?

Algorithms

The pair sum of a pair <code>(a,b)</code> is equal to <code>a + b</code>. The maximum pair sum is the largest pair sum in a list of pairs.

<ul>
	<li>For example, if we have pairs <code>(1,5)</code>, <code>(2,3)</code>, and <code>(4,4)</code>, the maximum pair sum would be <code>max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8</code>.</li>
</ul>

Given an array <code>nums</code> of even length <code>n</code>, pair up the elements of <code>nums</code> into <code>n / 2</code> pairs such that:

<ul>
	<li>Each element of <code>nums</code> is in exactly one pair, and</li>
	<li>The maximum pair sum is minimized.</li>
</ul>

Return the minimized maximum pair sum after optimally pairing up the elements.

&nbsp;
Example 1:

<pre>
Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.
</pre>

Example 2:

<pre>
Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>n</code> is even.</li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

第 53 场双周赛

biweekly-contest-53

minPairSum

高级工程师

Minimize Maximum Pair Sum in Array

Greedy

Array

Two Pointers

Sorting

一对元素 <code>(a,b)</code> 的&nbsp;数对和&nbsp;等于 <code>a + b</code>。最大数对和&nbsp;是所有数对中最大的&nbsp;数对和。

<ul>
	<li>例如，如果有数对 <code>(1,5)</code>、<code>(2,3)</code> 和 <code>(4,4)</code>，那么&nbsp;最大数对和&nbsp;为 <code>max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8</code>。</li>
</ul>

给你一个长度为&nbsp;偶数 <code>n</code> 的数组 <code>nums</code>，请你将 <code>nums</code> 中的元素分成 <code>n / 2</code> 个数对，使得：

<ul>
	<li><code>nums</code> 中的每个元素&nbsp;恰好属于一个&nbsp;数对，并且</li>
	<li>最大数对和&nbsp;尽可能小。</li>
</ul>

请你返回最优配对方案下&nbsp;最大数对和&nbsp;的最小值。

&nbsp;

示例 1：

<pre>
输入：nums = [3,5,2,3]
输出：7
解释：可以将元素分成数对 (3,3) 和 (5,2)。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7。
</pre>

示例 2：

<pre>
输入：nums = [3,5,4,2,4,6]
输出：8
解释：可以将元素分成数对 (3,5)、(4,4) 和 (6,2)。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>n</code> 是&nbsp;偶数。</li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

数组中最大数对和的最小值

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

一对元素 (a,b) 的 数对和 等于 a + b。最大数对和 是所有数对中最大的 数对和。

 * 例如，如果有数对 (1,5)、(2,3) 和 (4,4)，那么 最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8。

给你一个长度为 偶数 n 的数组 nums，请你将 nums 中的元素分成 n / 2 个数对，使得：

 * nums 中的每个元素 恰好属于一个 数对，并且
 * 最大数对和 尽可能小。

请你返回最优配对方案下 最大数对和 的最小值。

 

示例 1：


输入：nums = [3,5,2,3]
输出：7
解释：可以将元素分成数对 (3,3) 和 (5,2)。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7。


示例 2：


输入：nums = [3,5,4,2,4,6]
输出：8
解释：可以将元素分成数对 (3,5)、(4,4) 和 (6,2)。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8。


 

提示：

 * n == nums.length
 * 2 <= n <= 105
 * n 是 偶数。
 * 1 <= nums[i] <= 105