最佳觀光組合

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中文網其他相關文章！