maximize-ysum-by-picking-a-triplet-of-distinct-xvalues

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given two integer arrays <code>x</code> and <code>y</code>, each of length <code>n</code>. You must choose three distinct indices <code>i</code>, <code>j</code>, and <code>k</code> such that:

<ul>
	<li><code>x[i] != x[j]</code></li>
	<li><code>x[j] != x[k]</code></li>
	<li><code>x[k] != x[i]</code></li>
</ul>

Your goal is to maximize the value of <code>y[i] + y[j] + y[k]</code> under these conditions. Return the maximum possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

&nbsp;
Example 1:

<div class="example-block">
Input: x = [1,2,1,3,2], y = [5,3,4,6,2]

Output: 14

Explanation:

<ul>
	<li>Choose <code>i = 0</code> (<code>x[i] = 1</code>, <code>y[i] = 5</code>), <code>j = 1</code> (<code>x[j] = 2</code>, <code>y[j] = 3</code>), <code>k = 3</code> (<code>x[k] = 3</code>, <code>y[k] = 6</code>).</li>
	<li>All three values chosen from <code>x</code> are distinct. <code>5 + 3 + 6 = 14</code> is the maximum we can obtain. Hence, the output is 14.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: x = [1,2,1,2], y = [4,5,6,7]

Output: -1

Explanation:

<ul>
	<li>There are only two distinct values in <code>x</code>. Hence, the output is -1.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == x.length == y.length</code></li>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= x[i], y[i] &lt;= 106</code></li>
</ul>

第 158 场双周赛

biweekly-contest-158

maxSumDistinctTriplet

高级工程师

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Maximum Sum of 3 Non-Overlapping Subarrays

maximum-sum-of-3-non-overlapping-subarrays

三个无重叠子数组的最大和

Largest Values From Labels

largest-values-from-labels

受标签影响的最大值

Greedy

Array

Hash Table

Sorting

Heap (Priority Queue)

给你两个整数数组 <code>x</code> 和 <code>y</code>，长度均为 <code>n</code>。你必须选择三个&nbsp;不同&nbsp;的下标&nbsp;<code>i</code>&nbsp;，<code>j</code> 和 <code>k</code>，满足以下条件：

<ul>
	<li><code>x[i] != x[j]</code></li>
	<li><code>x[j] != x[k]</code></li>
	<li><code>x[k] != x[i]</code></li>
</ul>

你的目标是在满足这些条件下&nbsp;最大化 <code>y[i] + y[j] + y[k]</code> 的值。返回通过选择这样一组三元组下标所能获得的&nbsp;最大&nbsp;可能和。

如果不存在这样的三元组，返回 -1。

&nbsp;

示例 1：

<div class="example-block">
输入：x = [1,2,1,3,2], y = [5,3,4,6,2]

输出：14

解释：

<ul>
	<li>选择 <code>i = 0</code>（<code>x[i] = 1</code>，<code>y[i] = 5</code>），<code>j = 1</code>（<code>x[j] = 2</code>，<code>y[j] = 3</code>），<code>k = 3</code>（<code>x[k] = 3</code>，<code>y[k] = 6</code>）。</li>
	<li>选出的三个 <code>x</code> 中的值互不相同。<code>5 + 3 + 6 = 14</code> 是我们能获得的最大值。因此输出为 14。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入：x = [1,2,1,2], y = [4,5,6,7]

输出：-1

解释：

<ul>
	<li><code>x</code> 中只有两个不同的值。因此输出为 -1。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>n == x.length == y.length</code></li>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= x[i], y[i] &lt;= 106</code></li>
</ul>