Bestes Sightseeing-Paar

1014. Bestes Sightseeing-Paar

Schwierigkeit:Mittel

Themen:Array, dynamische Programmierung

Sie erhalten ein ganzzahliges Array mit Werten, wobei Values[i] den Wert des i^ten Sehenswürdigkeiten darstellt. Zwei Sehenswürdigkeiten i und j haben einen Abstand j - i zwischen sich.

Die Punktzahl eines Paares (i < j) von Sehenswürdigkeiten beträgt Werte[i] Werte[j] i - j: die Summe der Werte der Sehenswürdigkeiten abzüglich der Entfernung zwischen ihnen.

Geben Sie die maximale Punktzahl für zwei Sehenswürdigkeiten zurück.

Beispiel 1:

• Eingabe: Werte = [8,1,5,2,6]
• Ausgabe: 11
• Erklärung: i = 0, j = 2, Werte[i] Werte[j] i - j = 8 5 0 - 2 = 11

Beispiel 2:

• Eingabe: Werte = [1,2]
• Ausgabe: 2

Einschränkungen:

• 2 <= Werte.Länge <= 5 * 10⁴
• 1 <= Werte[i] <= 1000

Hinweis:

1. Können Sie den besten Sehenswürdigkeitenpunkt in einem Durchgang erkennen (d. h. während Sie die Eingabe durchlaufen?). Was sollten wir speichern oder im Auge behalten, während wir dies iterieren?

Lösung:

Wir können einen Single-Pass-Ansatz mit einer linearen Zeitkomplexität O(n) verwenden. Die Idee besteht darin, die bestmöglichen Werte [i] i im Auge zu behalten, während wir das Array durchlaufen. Dadurch können wir die Punktewerte [i] Werte [j] i - j für jedes gültige Paar (i, j) maximieren.

Lassen Sie uns diese Lösung in PHP implementieren: 1014. Bestes Sightseeing-Paar

  
  
  Erläuterung:




Initialisierung:



maxI wird auf Werte[0] initialisiert, da wir mit der Auswertung von Paaren ab Index 1 beginnen.

maxScore wird auf 0 initialisiert, um die maximale Punktzahl zu verfolgen.



Über das Array iterieren:


Berechnen Sie für jeden Index j beginnend bei 1 die Punktzahl für das Paar (i, j) mithilfe der Formel:
Score = maxI-Werte[j] - j

maxScore mit dem erhaltenen Maximalwert aktualisieren.



MaxI aktualisieren:


Aktualisieren Sie maxI, um den maximal möglichen Wert von Werten[i] i für die nächsten Iterationen zu verfolgen.



Maximale Punktzahl zurückgeben:

Nach dem Durchlaufen des Arrays enthält maxScore die maximale Punktzahl für jedes Paar.





  
  
  Komplexität:




Zeitkomplexität: O(n) weil wir das Array einmal durchlaufen.

Raumkomplexität: O(1) da wir eine konstante Menge an Raum nutzen.


Diese Lösung berechnet effizient die maximale Punktzahl unter Einhaltung der Einschränkungen und ist für große Eingaben optimiert.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonBestes Sightseeing-Paar. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!