<jupyter_start><jupyter_text>说明：    给定正整数数组 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 提示：    1、2 <= A.length <= 50000    2、1 <= A[i] <= 1000<jupyter_code>class Solution:
    def maxScoreSightseeingPair(self, A) -> int:
        max_val = -float('inf')
        res = []
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                max_val = max(max_val, A[i] + A[j] + i - j)
        return max_val
# 为了使公式“ A[i]+ i + A [j] -j”最大化，我们可以注意到，对于任何索引“ j”，得分均以之前看到的“ A [i] + i”的最佳值最大化（因为“ A [j] -j“是固定的。
# 结果，我们可以进行一次O（n）循环，仅记住O（1）空间中“A[i] + i”的最大值，并更新我们观察到的记录得分（变量“最佳”） 。
class Solution:
    def maxScoreSightseeingPair(self, A) -> int:
        K = A[0]
        best = -float('inf')
        for j in range(1, len(A)):
            x = A[j]
            best = max(best, K + x - j) # A[i] + i + A[j] - j
            K = max(K, x + j) # A[j] + j
        return best
class Solution:
    def maxScoreSightseeingPair(self, A) -> int:
        arr = [A[0] + A[j] - j for j in range(1, len(A))] # 第 0 个景点 与其他所有景点 的得分
        max_dif = 0
        ans = max(arr)
        print(arr, ans)
        for j in range(1, len(arr)):
            max_dif = max(max_dif, A[j] + j - A[0]) # A[0] + A[j] + i - j
            print(A[j], j, A[0], A[j] + j - A[0])
            ans = max(ans, arr[j] + max_dif) # arr[j]
        return ans
class Solution:
    def maxScoreSightseeingPair(self, A) -> int:
        res = 0
        max_so_far = A[0] + 0
        for i in range(1, len(A)):
            res = max(res, max_so_far + A[i] - i) # A[0] + A[i] + i - j
            max_so_far = max(max_so_far, A[i] + i)
        return res
solution = Solution()
solution.maxScoreSightseeingPair([8,1,5,2,6])<jupyter_output>8
11
7
10
StarcoderdataJupyterStructuredCleanDedup