. Jumlah Maksimum Subarray Bertindih

689. Jumlah Maksimum 3 Subarray Tidak Bertindih

Kesukaran: Sukar

Topik: Tatasusunan, Pengaturcaraan Dinamik

Memandangkan nombor tatasusunan integer dan integer k, cari tiga subarray tidak bertindih dengan panjang k dengan jumlah maksimum dan kembalikannya.

Kembalikan hasilnya sebagai senarai indeks yang mewakili kedudukan permulaan setiap selang (0-diindeks). Jika terdapat berbilang jawapan, kembalikan yang terkecil dari segi leksikografi.

Contoh 1:

• Input: nombor = [1,2,1,2,6,7,5,1], k = 2
• Output: [0,3,5]
• Penjelasan: Subarrays [1, 2], [2, 6], [7, 5] sepadan dengan indeks permulaan [0, 3, 5].
  • Kita juga boleh mengambil [2, 1], tetapi jawapan bagi [1, 3, 5] akan lebih besar dari segi leksikografi.

Contoh 2:

• Input: nombor = [1,2,1,2,1,2,1,2,1], k = 2
• Output: [0,2,4]

Kekangan:

• 1 <= nums.length <= 2 * 10⁴
• 1 <= nums[i] < 2¹⁶
• 1 <= k <= lantai(bilangan panjang / 3)

Penyelesaian:

Kami akan menggunakan pendekatan pengaturcaraan dinamik. Ideanya adalah untuk memecahkan masalah kepada submasalah yang lebih kecil, memanfaatkan pertindihan sub-baris untuk mengira dengan cekap jumlah maksimum tiga sub-baris tidak bertindih panjang k.

Pendekatan:

1. Prakira jumlah subarray panjang k:
   Pertama, kita mengira jumlah semua subarray panjang k dalam nombor tatasusunan input. Ini boleh dilakukan dengan cekap dalam masa linear dengan menggunakan teknik tetingkap gelongsor.

2. Pengaturcaraan Dinamik (DP):
   Kami mencipta dua tatasusunan tambahan, kiri dan kanan, untuk menyimpan indeks subarray terbaik yang ditemui sehingga kedudukan semasa. Bahagian kiri[i] akan menyimpan indeks subarray terbaik yang berakhir sebelum indeks i, dan kanan[i] akan menyimpan indeks subarray terbaik bermula selepas indeks i.

3. Lelar dan Kira Jumlah Maksimum:
   Untuk setiap subarray tengah yang mungkin bermula pada indeks j, kami mengira jumlah keseluruhan dengan mempertimbangkan subarray kiri terbaik sebelum j dan subarray kanan terbaik selepas j.

4. Penyusunan Leksikografi:
   Jika terdapat berbilang jawapan yang sah (dengan jumlah yang sama), kami mengembalikan yang terkecil dari segi leksikografi. Ini dipastikan dengan tertib lelaran.

Mari laksanakan penyelesaian ini dalam PHP: 689. Jumlah Maksimum 3 Subarray Tidak Bertindih

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>Pengiraan Jumlah Subarray:</strong></p>

<ul>
<li>Kami mengira jumlah semua subarray yang mungkin bagi panjang k. Ini dilakukan dengan terlebih dahulu mengira jumlah unsur k pertama. Kemudian, untuk setiap kedudukan seterusnya, kami menolak elemen yang tertinggal dan menambah elemen seterusnya dalam tatasusunan, menjadikannya pendekatan tetingkap gelongsor yang cekap.</li>
</ul>
</li>
<li>
<p><strong>Turutan Kiri dan Kanan:</strong></p>

<ul>
<li>
kiri[i] memegang indeks subarray dengan jumlah maksimum yang berakhir sebelum indeks i.</li>
<li>
kanan[i] memegang indeks subarray dengan jumlah maksimum yang bermula selepas indeks i.</li>
</ul>
</li>
<li>
<p><strong>Pengiraan Akhir:</strong></p>

<ul>
<li>Untuk setiap subarray tengah j, kami menyemak gabungan subarray kiri terbaik dan subarray kanan terbaik, dan mengemas kini keputusan jika jumlahnya lebih besar daripada maksimum semasa.</li>
</ul>
</li>
<li>
<p><strong>Jawapan Terkecil Dari segi Leksikografi:</strong></p>

<ul>
<li>Sambil kami melelakan dari kiri ke kanan, kami memastikan penyelesaian terkecil dari segi leksikografi dengan secara semula jadi memilih subarray pertama yang menghasilkan jumlah maksimum.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Contoh:
</h3>

<p>Untuk input:<br>
</p>

<pre class="brush:php;toolbar:false">$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

Outputnya ialah:

[0, 3, 5]

Pendekatan ini memastikan kerumitan masa kekal cekap, dengan kerumitan masa lebih kurang O(n), dengan n ialah panjang nombor tatasusunan input.

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 . Jumlah Maksimum Subarray Bertindih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!