一天一大 leet(最佳观光组合)难度:中等 DAY-17

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

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  let _result = 0,
    middleValue = A[0] + 0
  for (let i = 1; i < A.length; i++) {
    _result = Math.max(A[i] + middleValue - i, _result)
    middleValue = Math.max(middleValue, A[i] + i)
  }
  return _result
}

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  var ans = 0, mx = A[0] + 0;
  for (int j = 1; j < A.length; ++j) {
      ans = max(ans, mx + A[j] - j);
      // 边遍历边维护
      mx = max(mx, A[j] + j);
  }
  return ans;
}

/**
 * @param {number[]} A
 * @return {number}
 */
var maxScoreSightseeingPair = function (A) {
  let res = 0,
    prev = 0
  for (let i = 1; i < A.length; i++) {
    //prev是前i-1个元素中A[m]+m的最大值
    prev = Math.max(prev, A[i - 1] + i - 1) 
    res = Math.max(res, prev + A[i] - i)
  }
  return res
}