Programme JavaScript pour trouver la valeur maximale de Sum( i*arr), autorisant uniquement la rotation du tableau donné

Nous utiliserons des méthodes mathématiques pour trouver la valeur maximale de la somme des produits de l'indice et des valeurs des éléments du tableau. En faisant tourner le tableau, nous pouvons maximiser cette somme en plaçant la valeur maximale du tableau à l'index avec le plus grand produit. L'algorithme que nous utiliserons consiste à trouver la somme des produits de l'index multiplié par les valeurs des éléments, puis à ajouter à cette somme la différence entre cette somme et le produit de la longueur du tableau multiplié par la somme des valeurs de l'index.

À l'avenir, nous continuerons à appliquer cet algorithme à différents tableaux pour trouver la valeur maximale de la somme de l'indice et du produit des valeurs des éléments permettant uniquement la rotation. Cette solution est très efficace car elle ne nécessite qu’un seul passage à travers le tableau et a une complexité temporelle de O(n). En utilisant cet algorithme, nous pouvons trouver rapidement et facilement la somme maximale des produits des index et des valeurs des éléments du tableau.

Méthode

• La somme de toutes les rotations peut être obtenue en multipliant chaque élément du tableau par son index correspondant et en additionnant les résultats.

• La valeur maximale peut être obtenue en trouvant l'index de la valeur maximale et en faisant pivoter le tableau de manière à ce que la valeur maximale soit le premier élément.

• La valeur maximale peut être trouvée en additionnant la valeur de chaque élément multipliée par son indice et en la comparant à la valeur maximale actuelle.

• La somme de tous les tours peut être trouvée en ajoutant la somme de tous les tours à la somme actuelle et en divisant par le nombre de tours.

• Peut renvoyer la valeur maximale comme résultat.

Exemple

La solution à ce problème consiste d'abord à trouver la somme de tous les éléments du tableau, puis à parcourir le tableau pivoté et à mettre à jour la somme en ajoutant la différence de la rotation actuelle à la somme précédente. La somme maximale est la réponse. Voici un exemple JavaScript complet -

function maxSum(arr) {
   let n = arr.length;
   let arrSum = 0;
   let currVal = 0;
   for (let i = 0; i < n; i++) {
      arrSum += arr[i];
      currVal += i * arr[i];
   }
   let maxVal = currVal;
   for (let j = 1; j < n; j++) {
      currVal = currVal + arrSum - n * arr[n - j];
      maxVal = Math.max(maxVal, currVal);
   }
   return maxVal;
}
let arr = [1, 20, 2, 10];
console.log(maxSum(arr)); // Output: 72

Instructions

La fonction

• maxSum prend un tableau en entrée et renvoie la somme maximale qui peut être obtenue en faisant pivoter le tableau et en prenant la somme de i * arr[i] pour chaque rotation.

• Variable n stocke la longueur du tableau.

• La variable arrSum stocke la somme de tous les éléments du tableau et est initialisée à 0.

• La variable currVal stocke la somme de i * arr[i] pour la rotation en cours et est initialisée à 0.

• La première boucle calcule la somme de tous les éléments du tableau et la somme de i * arr[i] pour la première rotation.

• La variable maxVal stocke la somme maximale et est initialisée à currVal.

• La deuxième boucle fait pivoter le tableau de manière itérative et met à jour la somme de i * arr[i] pour chaque rotation. La somme de i * arr[i] pour la rotation actuelle est mise à jour en ajoutant la différence de la rotation actuelle à la somme précédente.

La valeur de

• currVal est mise à jour en ajoutant la différence entre la somme de i * arr[i] pour la rotation actuelle et la somme de i * arr[i] pour la rotation précédente. La différence est calculée en soustrayant n * arr[n - j] de arrSum.

• La valeur maximale de currVal pour chaque tour est stockée dans maxVal à ​​l'aide de la fonction Math.max.

• Finally renvoie la valeur de maxVal comme réponse.

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!