Saya Matriks Hebat

1975. Jumlah Matriks Maksimum

Kesukaran: Sederhana

Topik: Tatasusunan, Tamak, Matriks

Anda diberi matriks n x n integer. Anda boleh melakukan operasi berikut beberapa kali:

• Pilih mana-mana dua bersebelahan elemen matriks dan darab setiap satu daripadanya dengan -1.

Dua elemen dianggap bersebelahan jika dan hanya jika mereka berkongsi sempadan.

Matlamat anda adalah untuk memaksimumkan penjumlahan elemen matriks. Kembalikan jumlah maksimum elemen matriks menggunakan operasi yang dinyatakan di atas.

Contoh 1:

• Input: matriks = [[1,-1],[-1,1]]
• Output: 4
• Penjelasan: Kita boleh mengikuti langkah berikut untuk mencapai jumlah bersamaan 4:
  • Darabkan 2 elemen dalam baris pertama dengan -1.
  • Darabkan 2 elemen dalam lajur pertama dengan -1.

Contoh 2:

• Input: matriks = [[1,2,3],[-1,-2,-3],[1,2,3]]
• Output: 16
• Penjelasan: Kita boleh mengikuti langkah berikut untuk mencapai jumlah bersamaan 16:
  • Darabkan 2 elemen terakhir dalam baris kedua dengan -1.

Kekangan:

• n == matriks.panjang == matriks[i].panjang
• 2 <= n <= 250
• -10⁵ <= matriks[i][j] <= 10⁵

Petunjuk:

1. Cuba gunakan operasi supaya setiap baris hanya mempunyai satu nombor negatif.
2. Jika anda hanya mempunyai satu unsur negatif, anda tidak boleh menukarnya kepada positif.

Penyelesaian:

Untuk memaksimumkan jumlah matriks menggunakan operasi, kita perlu meminimumkan nilai mutlak sumbangan negatif kepada jumlah itu. Inilah rancangannya:

1. Kira Nombor Negatif: Jejaki bilangan nombor negatif yang terdapat dalam matriks.
2. Cari Nilai Mutlak Minimum: Tentukan nilai mutlak terkecil dalam matriks, yang akan membantu jika bilangan negatif adalah ganjil.
3. Laraskan untuk Negatif Ganjil: Jika kiraan nombor negatif adalah ganjil, nilai mutlak terkecil tidak boleh ditukar kepada positif, dan ini mengehadkan jumlah maksimum yang mungkin.

Mari kita laksanakan penyelesaian ini dalam PHP: 1975. Jumlah Matriks Maksimum

  
  
  Penjelasan:




Penjumlahan Nilai Mutlak: Kira jumlah nilai mutlak semua elemen sejak konfigurasi optimum membalikkan seberapa banyak nombor negatif kepada positif yang mungkin.

Jejaki Nilai Mutlak Terkecil: Gunakan ini untuk melaraskan jumlah apabila kiraan nombor negatif adalah ganjil.

Kendalikan Negatif Ganjil: Tolak dua kali nilai mutlak terkecil daripada jumlah untuk mengambil kira unsur negatif yang tidak dapat dielakkan apabila negatif tidak dapat dinetralkan sepenuhnya.



  
  
  Kerumitan




Kerumitan Masa: O(n^2), kerana matriks dilalui sekali.

Kerumitan Angkasa: O(1), kerana tiada ruang tambahan digunakan selain daripada pembolehubah.


Penyelesaian ini berfungsi dengan cekap dalam kekangan yang diberikan.

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 Saya Matriks Hebat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!