题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

提示：

2 <= values.length <= 5 * 104
1 <= values[i] <= 1000

解答

我们再看一眼优化公式：A[i]+A[j]+i-j，分成两部分看，(A[i]+i)-(A[j]-j)，这样就清楚了，每个位置A[i]+i和A[j]-j都是固定的，优化问题就转化为：
maximize(A[i]+i)+maximize(A[j]+j)，s.t. i<j
也就是说，寻找两个位置i<j，能够使得A[i]+i和A[j]-j最大。

我们完全可以一次遍历实现查找过程。一遍遍历，一边寻找最大的A[i]+i和A[j]-j，为了满足i<j的条件，我们只对A[i]+i做缓存ai_plus_i ，每次遍历都及时更新ai_plus_i 和最终结果。

class Solution:
    def maxScoreSightseeingPair(self, A):
        res = 0
        ai_plus_i = A[0] + 0
        for j in range(1, len(A)):
            res = max(res, ai_plus_i + A[j] - j)
            ai_plus_i = max(ai_plus_i, A[j] + j)
        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析