Program JavaScript untuk mengira saiz subarray dengan jumlah maksimum

Program JavaScript untuk mencari saiz maksimum dan subarray adalah masalah biasa dalam bidang pengaturcaraan, terutamanya dalam pembangunan web. Pernyataan masalah melibatkan mencari subarray bersebelahan dengan jumlah maksimum dalam tatasusunan integer satu dimensi tertentu. Ini juga dikenali sebagai masalah subarray maksimum. Menyelesaikan masalah ini berguna dalam pelbagai aplikasi, seperti analisis kewangan, ramalan pasaran saham dan pemprosesan isyarat.

Dalam artikel ini, kita akan melihat algoritma dan saiz subarray untuk jumlah maksimum menggunakan JavaScript. Kami mula-mula akan membincangkan masalah secara terperinci dan kemudian meneruskan untuk membangunkan penyelesaian langkah demi langkah menggunakan bahasa pengaturcaraan JavaScript. Jadi mari kita mulakan!

Pernyataan Masalah

Memandangkan tatasusunan integer, kita perlu mencari panjang sub-tatasusunan dengan jumlah maksimum.

Sebagai contoh, katakan kita mempunyai tatasusunan integer: [1, -2, 1, 1, -2, 1], subarari terbesar ialah [1, 1], dan jumlahnya ialah 2. Kita boleh mencari panjang subarray ini dengan menolak indeks permulaan daripada indeks akhir dan menambah 1. Dalam contoh ini, indeks permulaan ialah 0 dan indeks berakhir ialah 1, jadi panjang subarray ialah 2.

Contoh lain ialah tatasusunan semua integer negatif: [-2, -5, -8, -3, -1, -7]. Dalam kes ini, subarray terbesar ialah [-1] dan jumlahnya ialah -1. Memandangkan semua elemen adalah negatif, subarray dengan nilai mutlak terkecil mempunyai jumlah terbesar. Oleh itu, panjang subarray ialah -1.

Perlu diingat bahawa mungkin terdapat berbilang subarray maksimum, setiap satu dengan jumlah yang sama. Walau bagaimanapun, kita hanya perlu mencari salah satu daripada mereka.

Algoritma

Langkah 1

Kami mula-mula memulakan empat pembolehubah: "maxSum" ialah "-Infinity", "currentSum" ialah "0", "start" ialah "0", dan tamat ialah "0". Kami akan menggunakan 'maxSum' untuk menjejaki jumlah terbesar yang kami lihat setakat ini, 'currentSum' untuk mengira jumlah subarray untuk lelaran semasa kami, 'start' untuk menjejaki indeks permulaan subarray, dan 'tamat' untuk menjejaki Indeks akhir subarray.

Langkah 2

Kemudian kami menggunakan gelung "untuk" untuk mengulangi tatasusunan. Untuk setiap elemen dalam tatasusunan, kami menambahnya pada "currentSum". Jika 'currentSum' lebih besar daripada 'maxSum', kami mengemas kini 'maxSum' kepada 'currentSum' dan menetapkan 'end' kepada indeks semasa.

Langkah 3

Seterusnya, kami menggunakan gelung sementara untuk menyemak sama ada "currentSum" kurang daripada "0". Jika ya, kita tolak nilai pada "mula" daripada "currentSum" dan tambah 1 kepada "mula". Ini memastikan bahawa kita sentiasa mempunyai subset tatasusunan yang bersebelahan.

Langkah 4

Akhir sekali, kami menyemak sama ada "currentSum" adalah sama dengan "maxSum" dan jika saiz subarray semasa lebih besar daripada subarray sebelumnya. Jika ya, kami mengemas kini "tamat" kepada indeks semasa.

Langkah 5

Kerumitan masa algoritma ini ialah O(n) dan kerumitan ruang ialah O(1), yang optimum untuk masalah ini.

Contoh

Atur cara JavaScript berikut direka bentuk untuk menyelesaikan masalah menggunakan dua penunjuk, mula dan tamat, untuk mencari subarray bersebelahan dengan jumlah terbesar dalam tatasusunan integer. Algoritma ini memulakan jumlah maksimum kepada infiniti negatif, jumlah semasa kepada sifar, dan indeks permulaan dan akhir kepada sifar. Ia menambah setiap elemen kepada jumlah semasa dan mengemas kini jumlah maksimum dan indeks akhir jika jumlah semasa lebih besar daripada jumlah maksimum. Ia mengalih keluar elemen dari permulaan subarray sehingga jumlah semasa tidak lagi negatif, kemudian mengemas kini indeks akhir jika jumlah semasa adalah sama dengan jumlah maksimum dan panjang subarray lebih besar daripada panjang subarray sebelumnya. Akhirnya, ia mengembalikan panjang subarray terbesar dengan menolak indeks permulaan daripada indeks akhir dan menambah 1.

function maxSubarraySize(arr) {
   let maxSum = -Infinity;
   let currentSum = 0;
   let start = 0;
   let end = 0;
   for (let i = 0; i < arr.length; i++) {
      currentSum += arr[i];
      if (currentSum > maxSum) {
         maxSum = currentSum;
         end = i;
      }
      while (currentSum < 0) {
         currentSum -= arr[start];
         start++;
      }
      if (currentSum === maxSum && i - start > end - start) {
         end = i;
      }
   }
   return end - start + 1;
} 
// Example usage:
const arr = [1, -2, 1, 1, -2, 1];
console.log("Array:", JSON.stringify(arr));
const size = maxSubarraySize(arr);
console.log("Size of the Subarray with Maximum Sum:", size);

Mari lihat output dengan beberapa contoh untuk pemahaman yang lebih baik.

Contoh 1

Input - Diberi tatasusunan integer, a[]= {1, -2, 1, 1, -2, 1}

Output− 2

Penerangan - Subarray dengan elemen berturut-turut dengan jumlah maksimum {1, 1}. Oleh itu, panjangnya ialah 2.

Contoh 2

Input - Diberi tatasusunan semua integer negatif, a[]= {-2, -5, -8, -3, -1, -7}

Output-1

Penjelasan - Dalam kes ini, subarray maksimum ialah [-1] dan jumlahnya ialah -1. Oleh itu, panjang subarray ialah -1.

Kesimpulan

Saiz subarray dengan jumlah terbesar adalah soalan biasa apabila bekerja dengan tatasusunan dalam pengaturcaraan. Algoritma untuk menyelesaikan masalah ini melibatkan lelaran pada tatasusunan dan menjejaki jumlah semasa dan jumlah terbesar yang dilihat setakat ini. Dengan melaksanakan algoritma ini dalam JavaScript, kita boleh menulis atur cara yang cekap mencari saiz subarray yang mempunyai jumlah terbesar untuk mana-mana tatasusunan integer tertentu.

Atas ialah kandungan terperinci Program JavaScript untuk mengira saiz subarray dengan jumlah maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!