最佳观光组合

1014。最佳观光配对

难度：中等

主题：数组，动态规划

给你一个整数数组values，其中values[i]代表第i^个个景点的值。两个景点 i 和 j 之间的距离为 j - i。

一对（i

返回一对游览点的最高分。

示例1：

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

示例2：

• 输入：值= [1,2]
• 输出： 2

约束：

• 2 4
• 1

提示：

1. 你能一次性说出最好的观光景点吗（即，当你迭代输入时？）当我们迭代执行此操作时，我们应该存储或跟踪什么？

解决方案：

我们可以使用具有线性时间复杂度的单遍方法O(n)。这个想法是在我们迭代数组时跟踪最好的可能值[i] i。这使我们能够最大化每个有效对 (i, j) 的分值[i]值[j] i - j。

让我们用 PHP 实现这个解决方案：1014。最佳观光配对

<?php /**
 * @param Integer[] $values
 * @return Integer
 */
function maxScoreSightseeingPair($values) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$values1 = [8, 1, 5, 2, 6];
echo maxScoreSightseeingPair($values1); // Output: 11

$values2 = [1, 2];
echo maxScoreSightseeingPair($values2); // Output: 2
?>

解释：

1. 初始化：

   • maxI 被初始化为values[0]，因为我们从索引1开始评估对。
   • maxScore 初始化为 0 以跟踪最高分数。

2. 迭代数组：

   • 对于从 1 开始的每个索引 j，使用以下公式计算 (i, j) 对的分数： 分数 = maxI 值[j] - j
   • 用获得的最大值更新 maxScore。

3. 更新 maxI：

   • 更新 maxI 以跟踪下一次迭代的 value[i] i 的最大可能值。

4. 返回最高分数：

   • 迭代数组后，maxScore 将包含任何对的最大分数。

复杂：

• 时间复杂度： O(n) 因为我们循环遍历数组一次。
• 空间复杂度： O(1)，因为我们使用恒定的空间量。

该解决方案在遵守约束的同时有效计算最大分数，并针对大输入进行了优化。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是最佳观光组合的详细内容。更多信息请关注PHP中文网其他相关文章！