难度:中等 关键词:数组
⭐️⭐️⭐️
给定正整数数组 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 = (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