1014.最佳观光组合

链接：1014.最佳观光组合
难度：Medium
标签：数组、动态规划
简介：给定正整数数组  A，A[i]  表示第 i 个观光景点的评分，并且两个景点  i 和  j  之间的距离为  j - i。一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。

题解 1 - typescript

• 编辑时间：2020-06-17
• 执行用时：8640ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：暴力运算。

function maxScoreSightseeingPair(A: number[]): number {
  const len = A.length;
  let max = 0;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      const num = comp(i, j);
      if (num > max) max = num;
    }
  }
  return max;
  function comp(i: number, j: number): number {
    return A[i] + A[j] + i - j;
  }
}

题解 2 - typescript

• 编辑时间：2020-06-17
• 执行用时：324ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：在题解 1 的基础上增加小于 0 的值的判断，若小于 0 则跳出当前循环。

function maxScoreSightseeingPair(A: number[]): number {
  const len = A.length;
  let max = 0;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      const num = comp(i, j);
      if (num > max) max = num;
      if (num < 0) break;
    }
  }
  return max;
  function comp(i: number, j: number): number {
    return A[i] + A[j] + i - j;
  }
}

题解 3 - typescript

• 编辑时间：2020-06-17
• 执行用时：80ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：题目转化为 A[i]+i+A[j]-j,只要求出最大 A[i]+i，并于当前 i 值进行判断即可。

function maxScoreSightseeingPair(A: number[]): number {
  const len = A.length;
  let ans = 0;
  let mx = A[0];
  for (let i = 1; i < len; i++) {
    ans = Math.max(ans, mx + A[i] - i);
    mx = Math.max(mx, A[i] + i);
  }
  return ans;
}

题解 4 - python

• 编辑时间：2024-09-23
• 执行用时：119ms
• 内存消耗：21.2MB
• 编程语言：python
• 解法介绍：遍历时记录前面的最大值。

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        prev = values[0]
        res = 0
        for i in range(1, len(values)):
            res = max(res, prev - i + values[i])
            prev = max(prev, values[i] + i)
        return res