[1014] 最佳观光组合

details

解题思路：

1. 公式拆解： 我们可以将得分公式 A[i] + A[j] + i - j 进行拆分为：

   • A[i] + i（与位置 i 相关的部分）
   • A[j] - j（与位置 j 相关的部分）

   由于 j > i，即我们从左到右遍历数组，因此只需要记录之前景点的最大值 A[i] + i，并且在每一步都更新最佳观光组合的得分。

2. 贪心算法： 我们遍历数组 A，在每一步中：

   • 计算当前景点 j 的组合得分 A[j] - j + max(A[i] + i)。
   • 记录当前的最大观光组合得分。
   • 更新 max(A[i] + i)，以便在下一个景点计算时使用。

代码实现（JavaScript）：

function maxScoreSightseeingPair(A) {
    let maxScore = 0; // 记录最佳观光组合的得分
    let maxAiPlusI = A[0]; // 记录 A[i] + i 的最大值

    // 遍历每个景点 j，从第 1 个景点开始
    for (let j = 1; j < A.length; j++) {
        // 当前观光组合得分为 A[i] + A[j] + i - j
        // 即 maxAiPlusI + A[j] - j
        maxScore = Math.max(maxScore, maxAiPlusI + A[j] - j);

        // 更新 max(A[i] + i) 的值
        maxAiPlusI = Math.max(maxAiPlusI, A[j] + j);
    }

    return maxScore;
}

// 示例
const A = [8, 1, 5, 2, 6];
console.log(maxScoreSightseeingPair(A)); // 输出 11

解释：

• maxScore：保存最佳观光组合的最大得分。
• maxAiPlusI：在遍历时保存 A[i] + i 的最大值。
• 每一步通过 maxScore = Math.max(maxScore, maxAiPlusI + A[j] - j) 计算最佳组合分数。
• maxAiPlusI = Math.max(maxAiPlusI, A[j] + j) 更新 A[i] + i 的最大值，供后续计算使用。

复杂度分析：

• 时间复杂度：O(n)，因为只需要遍历数组一次。
• 空间复杂度：O(1)，我们只用了常数空间。