Pasangan Persiaran Terbaik

1014. Pasangan Persiaran Terbaik

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik

Anda diberi nilai tatasusunan integer di mana nilai[i] mewakili nilai tempat persiaran^ke. Dua tempat persiaran i dan j mempunyai jarak j - i antaranya.

Skor sepasang (i < j) tempat persiaran ialah nilai[i] nilai[j] i - j: jumlah nilai tempat persiaran, tolak jarak antara mereka.

Kembali skor maksimum sepasang tempat persiaran.

Contoh 1:

• Input: nilai = [8,1,5,2,6]
• Output: 11
• Penjelasan: i = 0, j = 2, nilai[i] nilai[j] i - j = 8 5 0 - 2 = 11

Contoh 2:

• Input: nilai = [1,2]
• Output: 2

Kekangan:

• 2 <= values.length <= 5 * 10⁴
• 1 <= nilai[i] <= 1000

Petunjuk:

1. Bolehkah anda memberitahu tempat persiaran terbaik dalam satu laluan (cth. semasa anda mengulangi input?) Apakah yang perlu kami simpan atau jejaki semasa kami bergerak untuk melakukan ini?

Penyelesaian:

Kita boleh menggunakan pendekatan satu laluan dengan kerumitan masa linear O(n). Ideanya adalah untuk menjejaki nilai terbaik yang mungkin[i] i semasa kita melelakan melalui tatasusunan. Ini membolehkan kami memaksimumkan nilai skor[i] nilai[j] i - j untuk setiap pasangan yang sah (i, j).

Mari laksanakan penyelesaian ini dalam PHP: 1014. Pasangan Persiaran Terbaik

  
  
  Penjelasan:




Permulaan:



maxI dimulakan kepada nilai[0] kerana kami mula menilai pasangan dari indeks 1.

maxScore dimulakan kepada 0 untuk menjejak markah maksimum.



Lelaran Atas Tatasusunan:


Untuk setiap indeks j bermula dari 1, hitung skor untuk pasangan (i, j) menggunakan formula:
Skor = nilai maxI[j] - j

Kemas kini maxScore dengan nilai maksimum yang diperolehi.



Kemas kini maksimum:


Kemas kini maxI untuk menjejak nilai maksimum yang mungkin bagi nilai[i] i untuk lelaran seterusnya.



Kembalikan Markah Maksimum:

Selepas melelaran melalui tatasusunan, maxScore akan mengandungi skor maksimum untuk mana-mana pasangan.





  
  
  Kerumitan:




Kerumitan Masa: O(n) kerana kita menggelung melalui tatasusunan sekali.

Kerumitan Angkasa: O(1) kerana kami menggunakan jumlah ruang yang tetap.


Penyelesaian ini mengira skor maksimum dengan cekap sambil mematuhi kekangan dan dioptimumkan untuk input yang besar.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Pasangan Persiaran Terbaik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!