题目地址：https://leetcode.com/problems/best-sightseeing-pair/
题目描述
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.
Thescore 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: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
Note:
1、 2<=A.length<=50000；
2、 1<=A[i]<=1000；
题目大意
对于数组中的两个下标i, j，求A[i] + A[j] + i - j最大值.
解题方法
一般暴力解法是两重循环，即先找到一个位置 i 之后，从其后位置 j 继续循环遍历，这样的复杂度是O(N ^ 2) 的。看到题目给出的数据范围，数组的长度是 50000， 对于这个题O(N ^ 2) 的时间复杂度肯定不可取。
对于这个题，我们知道肯定只能用 O(N) 的解法，把公式稍加变化成(A[i] + i) + (A[j] - j)，我们可以看出要找出这两部分和的最大值。
具体方法是保存每个位置 j ，时刻维护其前面的A[i] + i的最大值出现的位置 pre_i。最后结果就是对于每个位置j对应的A[i] + A[j] + i - j最大值。
Python代码如下：
class Solution(object):
def maxScoreSightseeingPair(self, A):
"""
:type A: List[int]
:rtype: int
"""
pre_i = 0
res = 0
for j in range(1, len(A)):
res = max(A[j] - j + A[pre_i] + pre_i, res)
if A[j] + j > A[pre_i] + pre_i:
pre_i = j
return res
1 2 3 4 5 6 7 8 9 10 11 12 13
参考资料：https://leetcode.com/problems/best-sightseeing-pair/discuss/260850/JavaC%2B%2BPython-One-Pass
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发