Program JavaScript untuk mencari jumlah maksimum i*arr antara semua putaran tatasusunan yang diberikan

Dalam artikel ini, kami akan melaksanakan program JavaScript untuk mencari jumlah maksimum i*arr[i] antara semua putaran tatasusunan yang diberikan. Di sini i*arr[i] bermaksud kita ingin memaksimumkan jumlah semua elemen tatasusunan dengan mendarabnya dengan elemen pada kedudukan semasa. Kita boleh memutarkan elemen tatasusunan yang diberikan ke kiri atau kanan untuk mendapatkan jawapan maksimum. Untuk soalan ini, kami akan memberikan kod lengkap dan penjelasan terperinci.

Pengenalan kepada masalah

Dalam soalan ini, kita diberikan tatasusunan, jika kita mendarab semua elemen dengan nombor indeks yang sepadan dan kemudian menambah jumlah semua elemen, kita akan mendapat nombor. Dengan satu putaran, kita boleh mengalihkan elemen paling kiri atau paling kanan ke sisi bertentangan tatasusunan, yang menyebabkan indeks setiap elemen berubah, dan kita boleh memutar tatasusunan beberapa kali (tetapi selepas bilangan putaran adalah sama dengan panjang tatasusunan , kita akan mendapat tatasusunan yang sama seperti tatasusunan yang pertama), dengan memutar tatasusunan kita boleh menukar indeks unsur-unsur dan dengan itu jumlah i*arr[i].

Kami akan cuba memaksimumkan jumlah dengan dua pendekatan, pertama, mari kita lihat contoh −

Given array: 1 3 2 4 2
0th rotation sum: 1*0 + 3*1 + 2*2 + 4*3 + 2*4 = 27
1st rotation sum:  2*0 + 1*1 + 3*2 + 2*3 + 4*4  = 29
2nd rotation sum: 4*0 + 2*1 + 1*2 + 3*3 + 2*4 = 21
3rd rotation sum: 2*0 + 4*1 + 2*2 + 1*3 + 3*4 = 23 
4th rotation sum: 3*0 + 2*1 + 4*2 + 2*3 + 1*4 = 20

Kita dapat lihat bahawa pada pusingan pertama, kita mendapat jumlah tertinggi iaitu 29.

Kaedah

Terdapat dua cara untuk mendapatkan jumlah yang diperlukan, mari lihat kedua-duanya -

Kaedah 1 ialah pendekatan naif, kita akan menemui semua putaran tatasusunan dalam masa O(N), dan untuk setiap putaran, kita akan mencari jumlah semua elemen dalam masa O(N) dengan merentasi tatasusunan, manakala Tidak gunakan sebarang ruang tambahan.

Contoh

// function to find the maximum rotation sum
function maxSum(arr){
   var len = arr.length
   var ans = -10000000000 // variable to store the answer

   // for loop to find all the rotations of the array
   for(var i = 0; i < len; i++) {
      var cur_sum = 0;
      for(var j = 0; j <len ;j++) {
         cur_sum += j*arr[j];
      }
      if(ans < cur_sum){
         ans = cur_sum;
      }
      var temp = arr[len-1];
      var temp2
      for(var j=0; j<len; j++){
         temp2 = arr[j];
         arr[j] = temp;
         temp = temp2
      }
   }
   console.log("The required maximum sum is: " + ans)
}

// defining the array
arr = [1, 3, 2, 4, 2]
maxSum(arr)

Kerumitan masa dan kerumitan ruang

Kerumitan masa kod di atas ialah O(N*N) dengan N ialah saiz tatasusunan dan kerumitan ruang bagi kod di atas ialah O(1).

Pada setiap lelaran, kami hanya mempunyai perbezaan satu faktor untuk elemen terakhir sahaja kerana faktornya akan dikemas kini daripada panjang tatasusunan - 1 hingga 0 untuk elemen lain satu lagi faktor mereka akan ditambah Jadi kita boleh menulis kod sebagai −

Contoh

// function to find the maximum rotation sum
function maxSum(arr){
   var len = arr.length
   var ans = -10000000000 // variable to store the answer
   
   // for loop to find all the rotations of the array
   var total_sum = 0;
   for (var i=0; i<len; i++){
      total_sum += arr[i];
   }
   var cur_val = 0;
   for (var i=0; i<len; i++){
      cur_val += i*arr[i];
   }
   
   // Initialize result
   var ans = cur_val;
   
   // Compute values for other iterations
   for (var i=1; i<len; i++) {
      var val = cur_val - (total_sum - arr[i-1]) + arr[i-1] * (len-1);
      cur_val = val;
      if(ans < val) {
         ans = val
      }
   }
   console.log("The required maximum sum is: " + ans)
}

// defining the array
arr = [1, 3, 2, 4, 2]
maxSum(arr)

Kerumitan masa dan kerumitan ruang

Kerumitan masa kod di atas ialah O(N), di mana N ialah saiz tatasusunan dan kerumitan ruang bagi kod di atas ialah O(1) Pendekatan ini sangat baik berbanding dengan yang sebelumnya.

Kesimpulan

Dalam tutorial ini, kami telah melaksanakan program JavaScript untuk mencari jumlah maksimum i*arr[i] antara semua putaran tatasusunan yang diberikan. Kami melihat dua kaedah, satu ialah mencari semua putaran tatasusunan yang diberikan dan kemudian membandingkan hasil ungkapan i*arr[i] mereka. Dalam kaedah kedua, kami mengurangkan kerumitan masa daripada O(N*N) kepada O(N) dengan menggunakan kaedah matematik.

Atas ialah kandungan terperinci Program JavaScript untuk mencari jumlah maksimum i*arr antara semua putaran tatasusunan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!