Meilleure paire touristique

1014. Meilleure paire touristique

Difficulté :Moyen

Sujets :Array, programmation dynamique

Vous recevez un tableau de valeurs entières où valeurs[i] représente la valeur du i^ème lieu touristique. Deux sites touristiques i et j ont une distance j - i entre eux.

Le score d'une paire (i

Rendre le score maximum d'une paire de sites touristiques.

Exemple 1 :

• Entrée : valeurs = [8,1,5,2,6]
• Sortie : 11
• Explication : i = 0, j = 2, valeurs[i] valeurs[j] i - j = 8 5 0 - 2 = 11

Exemple 2 :

• Entrée : valeurs = [1,2]
• Sortie : 2

Contraintes :

• 2 4
• 1

Indice :

1. Pouvez-vous identifier le meilleur site touristique en un seul passage (c'est-à-dire lorsque vous parcourez les entrées ?) Que devons-nous stocker ou suivre pendant que nous itérons pour ce faire ?

Solution :

Nous pouvons utiliser une approche en un seul passage avec une complexité temporelle linéaire O(n). L'idée est de garder une trace des meilleures valeurs possibles[i] i lorsque nous parcourons le tableau. Cela nous permet de maximiser les valeurs de score[i] valeurs[j] i - j pour chaque paire valide (i, j).

Implémentons cette solution en PHP : 1014. Meilleure paire touristique

<?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
?>

Explication:

1. Initialisation :

   • maxI est initialisé à valeurs[0] car nous commençons à évaluer les paires à partir de l'index 1.
   • maxScore est initialisé à 0 pour suivre le score maximum.

2. Itérer sur le tableau :

   • Pour chaque indice j commençant à 1, calculez le score du couple (i, j) à l'aide de la formule : Score = valeurs maxI[j] - j
   • Mettez à jour maxScore avec la valeur maximale obtenue.

3. Mettre à jour maxI :

   • Mettez à jour maxI pour suivre la valeur maximale possible des valeurs[i] i pour les prochaines itérations.

4. Renvoyer le score maximum :

   • Après avoir parcouru le tableau, maxScore contiendra le score maximum pour n'importe quelle paire.

Complexité:

• Complexité temporelle : O(n) parce que nous parcourons le tableau une fois.
• Complexité spatiale : O(1) car nous utilisons une quantité constante d'espace.

Cette solution calcule efficacement le score maximum tout en respectant les contraintes et est optimisée pour les entrées volumineuses.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!