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 < j) de sites touristiques est égal aux valeurs[i] valeurs[j] i - j : la somme des valeurs des sites touristiques, moins la distance entre eux.

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 <= valeurs.longueur <= 5 * 10⁴
• 1 <= valeurs[i] <= 1000

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

  
  
  Explication:




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.



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.



Mettre à jour maxI :


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



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!