题目描述

给定正整数数组  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 = 8 + 5 + 0 - 2 = 11

提示：

略。

来源：LeetCode

思路

本题容易想到双重遍历，找出每一对 i，j 组合的解法。但是显然这不是一个好办法。

从双重遍历得到启发，每次遍历都是固定 i，然后 j 游动。我们把结果拆开来看，A[i] + A[j] + i - j可以分成A[i] + i和A[j] - j，结果只和 i，j 相关，其实我们在一次遍历的时候，只保留住当前最大的A[i] + i，然后和新的A[j] - j组合即可。

解法

/**
 * @param {number[]} A
 * @return {number}
 */
const maxScoreSightseeingPair = A => {
  let iValue = -Infinity;
  let result = -Infinity;

  for (let j = 0; j < A.length; j++) {
    result = Math.max(result, iValue + A[j] - j);
    iValue = Math.max(iValue, A[j] + j);
  }

  return result;
};