[leetcode] 1014. Best Sightseeing Pair

[leetcode] 1014. Best Sightseeing Pair

Description

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: [8,1,5,2,6]Output: 11Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

2 <= A.length <= 500001 <= A[i] <= 1000.

分析

题目的意思是：给你一个数组，找出最大的sightseeing pair对，即求下面的最大值：

A[i] + A[j] + i - j

这道题我暴力破解了一下，果然超时了，后面参考了一下别人的实现，global_max存放的就是遍历过程中的全局最大值，也是最后的结果，max_val存放的是第一个值，ma_inx就是对应的索引了。这里如果要更新max_val的话，要满足当前的值A[i]>=max_val+max_inx-i就行了，如果没有想到这个点就做不出来了。

代码

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

参考文献

​​[LeetCode] Easy Python solution beats 98%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。