LeetCode刷题DAY 31：最佳观光组

难度：中等 关键词：数组

⭐️⭐️⭐️

1 题目描述

给定正整数数组 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）。

2 题解

思路：数组变换

这道题可以用遍历、双指针、动态规划的方法求解，但看网友的分享后，发现一个最为奇妙的方法：A[i] + A[j] + i - j = (A[i] + i) + ( A[j] - j )，因此对于A[j] - j ，只需找到最大的A[i] + i即可，此处i<j。这里设置两个变量，每次遍历时，ans记录当前最大得分，max_value记录最大的A[i] + i。

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        if len(A)<2:
            return 0
        max_value = A[0]+0
        ans = 0
        for i in range(1,len(A)):
            if A[i]-i+max_value>ans:
                ans = A[i]-i+max_value
            if A[i]+i>max_value:
                max_value = A[i]+i
        return ans