1014. Best Sightseeing Pair¶
题目信息¶
- 题号:
1014
- 难度:
Medium
- 主题:
数组、下标对、评分最大化
- 原题:
- 重点:
选择满足
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。