难度: Medium
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6] 输出：11 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2] 输出：2
提示：
2 <= values.length <= 5 * 1041 <= values[i] <= 1000运行时间: 66 ms
内存: 21.0 MB
import sys
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
mx = values[0] + 0
res = sys.maxsize * -1 - 1
for i in range(1, len(values)):
cur = values[i] - i
if mx + cur > res:
res = mx + cur
if values[i] + i > mx:
mx = values[i] + i
return res
题解主要利用了一种贪心的思想和动态规划的思路。题目要求找出最大的 `values[i] + values[j] + i - j`（其中 i < j）。这个表达式可以重写为 `(values[i] + i) + (values[j] - j)`。这里，关键是实时维护最大的 `values[i] + i` 值（记为 mx），并计算每个 j 位置时与其对应的最大 `values[i] + i` 的和。在遍历过程中，不断更新 mx，并计算当前 j 位置的 `values[j] - j` 与 mx 的和，进而更新可能的最大结果。这种方法仅通过一次遍历完成计算，极大地提高了效率。
时间复杂度: O(n)
空间复杂度: O(1)
import sys
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
mx = values[0] + 0 # 初始化最大的 (values[i] + i)
res = sys.maxsize * -1 - 1 # 初始化最大分数的可能的最小值
for i in range(1, len(values)):
cur = values[i] - i # 当前位置的 values[j] - j
if mx + cur > res:
res = mx + cur # 更新最大观光组合得分
if values[i] + i > mx:
mx = values[i] + i # 更新 (values[i] + i) 的最大值
return res # 返回最大观光组合得分
这种分解方法不会遗漏任何可能的最大值组合，因为它只是将原始表达式重新组织，而没有改变其数学结构或意义。原表达式 `values[i] + values[j] + i - j` 通过将其拆分为 `values[i] + i` 和 `values[j] - j`，可以分别维护和计算，从而使我们能够实时追踪到目前为止的最大 `values[i] + i` 值（mx）。这种重写只是优化了计算过程，使得我们能够在单次遍历中即时更新和比较，而不影响结果的完整性和正确性。
当数组 `values` 只有一个元素时，算法的逻辑其实不会执行主要的遍历循环，因为循环从索引1开始。因此，这种情况下 `mx` 初始化为 `values[0]` 并不会产生任何负面影响。事实上，对于只有一个元素的数组，问题描述中的 `i < j` 条件直接导致没有有效的 `i` 和 `j` 可以用来形成观光组合，因此这种情况下代码可能需要额外的处理来直接返回0或其他特定值，表示没有有效的观光组合。
这种一次遍历的方法适用于所有可能的 `values` 数组配置，包括所有元素值非常接近或相等的情况。这是因为算法本质上是在寻找和维护过程中遇到的最大 `values[i] + i` 和相应 `values[j] - j` 的组合。即使所有元素的值非常接近，这种方法仍然能够有效地找到最佳的 `i` 和 `j` 组合（即使最终的最大值可能不会太高）。因此，算法的有效性和适用性并不受输入元素相似性的影响。