ベスト観光ペア

1014。ベスト観光ペア

難易度: 中

トピック: 配列、動的プログラミング

整数配列の値が与えられます。ここで、values[i] は i ^番目 の観光スポットの値を表します。 2 つの観光地 i と j の間には j - i の距離があります。

観光スポットのペア (i

観光スポットのペアの最大スコアを返します。

例 1:

• 入力: 値 = [8,1,5,2,6]
• 出力: 11
• 説明: i = 0、j = 2、values[i] value[j] i - j = 8 5 0 - 2 = 11

例 2:

• 入力: 値 = [1,2]
• 出力: 2

制約:

2 4 1

ヒント:

1 回のパス (つまり、入力を繰り返しながら) で最高の観光スポットを教えていただけますか?これを繰り返す際に何を保存または追跡する必要がありますか?

解決策:

線形時間計算量

O(n) によるシングルパス アプローチを使用できます。考え方は、配列を反復処理する際に、可能な限り最良の値[i] i を追跡することです。これにより、有効なペア (i, j) ごとにスコア value[i] value[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. 初期化:

   インデックス 1 からペアの評価を開始するため、maxI は value[0] に初期化されます。
   最大スコアを追跡するために、maxScore は 0 に初期化されます。

2. 配列の反復処理:

   1 から始まる各インデックス j について、次の式を使用してペア (i, j) のスコアを計算します。
   • スコア = maxI 値[j] - j
   取得した最大値で maxScore を更新します。

3. 最大値を更新:

   maxI を更新して、次の反復での value[i] i の最大可能値を追跡します。

4. 最大スコアを返す:

   • 配列を反復処理した後、maxScore には任意のペアの最大スコアが含まれます。

複雑：

• 時間計算量: O(n) 配列を 1 回ループするためです。
• 空間の複雑さ: O(1) 一定量の空間を使用するため。

このソリューションは、制約を遵守しながら最大スコアを効率的に計算し、大きな入力に対して最適化されています。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がベスト観光ペアの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。