Programme JavaScript permettant d'interroger la somme maximale de sous-tableaux consécutifs d'une longueur donnée dans un tableau pivoté

La rotation d'un tableau signifie que nous obtiendrons un nombre et que nous devrons déplacer les éléments du tableau vers la droite ou la gauche dans un ordre circulaire. Ici, nous ne précisons pas, nous utiliserons donc la rotation à droite comme critère, et après le nombre de rotations donné, nous renverrons le sous-tableau avec la plus grande somme. Nous verrons le code avec une explication correcte dans l'article.

Introduction au problème

Dans ce problème, nous obtenons un tableau contenant des entiers et un autre tableau contenant des paires de requêtes. Chaque index du tableau de requête contient deux entiers, le premier entier représente le nombre de rotations du tableau actuel et le deuxième entier représente la longueur du sous-tableau souhaité. Par exemple -

Si le tableau donné est [5, 7, 1, 4, 3, 8, 2] et que la requête est la suivante -

Queries: 3 rotations and size 3
After the three rotations, the array looks like: 3, 8, 2, 5, 7, 1, 4
From the above array, the result is 15 by subarray: 8, 2, and 5.
Queries: 2 rotations and size 4
After the two rotations, the array looks like: 8, 2, 5, 7, 1, 4, 3
From the above array, the result is 22 by subarrays 8, 2, 5, and 7

Passons aux solutions à ce problème

Méthode naïve

Le moyen le plus simple est d'utiliser directement deux boucles for pour implémenter le problème donné. Tout d’abord, nous allons nous déplacer sur le tableau et le faire pivoter dans le sens des aiguilles d’une montre un nombre de fois spécifié. Ensuite, nous trouvons les sous-tableaux d'une taille donnée et le sous-tableau avec la plus grande somme. Voyons son code -

Exemple

// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
   var n = arr.length 
   var temp = new Array(n)
   var j = 0;
   for(var i = n-rotations; i<n;i++){
      temp[j] = arr[i];
      j++;
   }
   for(var i = 0; i < n-rotations; i++){
      temp[j] = arr[i];
      j++;
   }
   
   // getting the size of the first window of the given size 
   var ans = -1000000000;
   for(var i = 0; i<=n-size; i++) {
      var cur = 0;
      for(var j = i; j < i+size; j++) {
         cur += temp[j];
      }
      if(ans < cur) {
         ans = cur;
      }
   }
   console.log("The maximum sum or given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}

// defining array 
var arr= [5, 7, 1, 4, 3, 8, 2]

// defining quries 
var queries = [[3,3], [2,4]]

// traversing over the array 
for(var i =0; i<queries.length; i++){
   subSum(arr, queries[i][0], queries[i][1]);
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(Q*D*N), où Q est le nombre de requêtes. D est la taille de chaque sous-tableau souhaité et N est la longueur du tableau.

La complexité spatiale du code ci-dessus est O(N) car nous utilisons un tableau supplémentaire pour stocker le tableau pivoté.

Méthode efficace

L'utilisation de la méthode de la fenêtre coulissante peut résoudre efficacement ce problème. Passons directement au code de cette question et obtenons-en un aperçu -

Exemple

// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
   var n = arr.length 
   var temp = new Array(n)
   var j = 0;
   for(var i = n-rotations; i<n;i++){
      temp[j] = arr[i];
      j++;
   }
   for(var i = 0; i < n-rotations; i++){
      temp[j] = arr[i];
      j++;
   }
   
   // getting the size of the first window of the given size 
   var ans = -1000000000
   var cur = 0;
   for(var i = 0;i<size;i++){
      cur += temp[i];
   }
   ans = cur;
   for(var i = size; i<n;i++){
      cur -= temp[i-size];
      cur += temp[i];
      if(ans < cur) {
         ans = cur;
      }
   }
   console.log("The maximum sum of given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}

// defining array 
var arr= [5, 7, 1, 4, 3, 8, 2]

// defining quries 
var queries = [[3,3], [2,4]]

// traversing over the array 
for(var i =0; i<queries.length; i++){
   subSum(arr, queries[i][0], queries[i][1]);
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(Q*N), où Q est le nombre de requêtes et N est la longueur du tableau.

La complexité spatiale du code ci-dessus est O(N) car nous utilisons un tableau supplémentaire pour stocker le tableau pivoté.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript permettant d'interroger afin de trouver la somme maximale de sous-tableaux consécutifs d'une longueur donnée dans un tableau pivoté. Nous avons implémenté une méthode naïve avec une complexité temporelle O(N*Q*D), puis l'avons améliorée en complexité temporelle O(N*Q) en utilisant le concept de fenêtres glissantes, mais la complexité spatiale des deux codes est identique à O(N) .

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!