Programme JavaScript pour trouver la somme maximale de i*arr parmi toutes les rotations d'un tableau donné

Dans cet article, nous allons implémenter un programme JavaScript pour trouver la somme maximale de i*arr[i] parmi toutes les rotations d'un tableau donné. Ici, i*arr[i] signifie que nous voulons maximiser la somme de tous les éléments du tableau en les multipliant par l'élément à la position actuelle. Nous pouvons faire pivoter les éléments du tableau donnés vers la gauche ou la droite pour obtenir la réponse maximale. Pour cette question, nous fournirons un code complet et une explication détaillée.

Introduction au problème

Dans cette question, on nous donne un tableau, si nous multiplions tous les éléments par leurs numéros d'index correspondants puis additionnons la somme de tous les éléments, nous obtiendrons un nombre. Avec une rotation, nous pouvons déplacer l'élément le plus à gauche ou le plus à droite vers le côté opposé du tableau, ce qui entraîne un changement de l'index de chaque élément, et nous pouvons faire pivoter le tableau un certain nombre de fois (mais après que le nombre de rotations soit égal à la longueur du tableau, nous obtiendrons le même tableau que le premier), en faisant tourner le tableau nous pouvons changer l'index des éléments et donc la somme de i*arr[i].

Nous allons essayer de maximiser la somme avec deux approches, d'abord, voyons l'exemple −

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

On voit qu'à la première rotation, on obtient la somme la plus élevée qui est la 29.

Méthode

Il existe deux façons de parvenir à trouver la somme requise, examinons les deux -

La méthode 1 est l'approche naïve, nous trouverons toutes les rotations du tableau en temps O(N), et pour chaque rotation, nous trouverons la somme de tous les éléments en temps O(N) en parcourant le tableau, tandis que utilisez tout espace supplémentaire.

Exemple

// 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)

Complexité temporelle et complexité spatiale

La complexité temporelle du code ci-dessus est O(N*N) où N est la taille du tableau et la complexité spatiale du code ci-dessus est O(1).

À chaque itération, nous n'avons qu'une différence d'un seul facteur pour le dernier élément uniquement parce que son facteur sera mis à jour à partir de la longueur du tableau - 1 à 0 pour les autres éléments, leur facteur supplémentaire sera ajouté. Nous pouvons donc écrire du code comme. −

Exemple

// 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)

Complexité temporelle et complexité spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la taille du tableau et la complexité spatiale du code ci-dessus est O(1). Cette approche est bien meilleure que la précédente.

.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour trouver la somme maximale de i*arr[i] parmi toutes les rotations d'un tableau donné. Nous avons vu deux méthodes, l'une consiste à trouver toutes les rotations d'un tableau donné, puis à comparer les résultats de leurs expressions i*arr[i]. Dans la deuxième méthode, nous réduisons la complexité temporelle de O(N*N) à O(N) en utilisant des méthodes mathématiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!