给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例：
输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
提示：
2 <= A.length <= 50000
1 <= A[i] <= 1000
自我解答(动态规划)
显然，最佳组合 (i, j), 其中 j 的位置，必定是列表中的其中一个，沿用 ”最大子序列和“ 中的简化思路，
将问题转化成 “求出以每个位置结尾的最佳组合分数“, 这样其中组合分数最大值，便是原问题的最优解。
但我发现 分数本身并不存在递推关系，反而在枚举组合时发现了规律：
假如枚举出 以 j 结尾的所有组合:
(0, j), (1, j) ... (j-1, j)
结合公式： A[i] + A[j] - (j - i)
(1, j) 相对于 (0, j) 来说，距离变近了，对于结果增益 +1
因此，很容易判断，即使 A[1] == A[0]，也可以直接选 i = 1,
事实上，只要 (A[1] + 距离增益) 不低于 A[0] 就行了
递推到 A[j-1]，便很容易从 A[0:j] 获得最佳起始位置
由此，便能一路记录最佳的起始位置，记作 best_start:
遍历到位置 j 时，通过 A[j] + (j - best_start) >= A[best_start] 更新 best_start
则以位置 j+1 结尾的最佳组合就是 (best_start, j+1)
到这里，最优子结构就很清晰了：
记 f(j): 以 位置 j 结尾的最佳起始位置
f(j+1) = j if A[j] + j - f(j) >= A[f(j)] else f(j)
由此写出 自底向上的动态规划算法
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
best_start, max_score = 0, A[1] + A[0] - 1
for i in range(1, len(A) - 1):
if A[i] + (i - best_start) >= A[best_start]:
best_start = i
score = A[i + 1] + A[best_start] - (i + 1 - best_start)
if score > max_score:
max_score = score
return max_score