best-sightseeing-pair

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>values</code> where values[i] represents the value of the <code>ith</code> sightseeing spot. Two sightseeing spots <code>i</code> and <code>j</code> have a distance <code>j - i</code> between them.

The score of a pair (<code>i &lt; j</code>) of sightseeing spots is <code>values[i] + values[j] + i - j</code>: the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

&nbsp;
Example 1:

<pre>
Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
</pre>

Example 2:

<pre>
Input: values = [1,2]
Output: 2
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= values.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= values[i] &lt;= 1000</code></li>
</ul>

maxScoreSightseeingPair

Best Sightseeing Pair

Array

Dynamic Programming

给你一个正整数数组 <code>values</code>，其中 <code>values[i]</code> 表示第 <code>i</code> 个观光景点的评分，并且两个景点 <code>i</code> 和 <code>j</code> 之间的 距离 为 <code>j - i</code>。

一对景点（<code>i < j</code>）组成的观光组合的得分为 <code>values[i] + values[j] + i - j</code> ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

 

示例 1：

<pre>
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
</pre>

示例 2：

<pre>
输入：values = [1,2]
输出：2
</pre>

 

提示：

<ul>
	<li><code>2 <= values.length <= 5 * 104</code></li>
	<li><code>1 <= values[i] <= 1000</code></li>
</ul>