1014. Best Sightseeing Pair

题目信息

题号:

1014

难度:

Medium

主题:

数组、下标对、评分最大化

原题:

LeetCode 1014

重点:

选择满足 i < j 的两个景点,得分为两处价值之和减去下标距离 j - i

题目重述

给定整数数组 values,values[i] 表示第 i 个景点的价值。选择两个不同景点 i 和 j,并要求 i < j。

这一对景点的得分定义为 values[i] + values[j] + i - j,也就是两个景点价值之和减去它们之间的下标距离。请返回所有合法景点对中的最大得分。

2 <= values.length <= 5 * 10^4,1 <= values[i] <= 1000。

自建示例

较远的高价值景点仍可能组成最优对:

输入:values = [4,7,2,8]
输出:13
解释:选择下标 1 和 3,得分为 7 + 8 + 1 - 3 = 13;其他任意下标对的得分都不超过 13。

数组只有两个景点:

输入:values = [1,9]
输出:9
解释:唯一可选下标对是 (0,1),得分为 1 + 9 - 1 = 9。