JavaScript 程序求给定数组所有旋转中 i*arr 的最大总和

王林转载: 2023-08-24 11:05:02 257浏览

在本文中，我们将实现JavaScript程序，用于找到给定数组的所有旋转中i*arr[i]的最大和。这里的i*arr[i]表示我们要通过将它们与当前位置的元素相乘来最大化数组所有元素的和。我们可以将给定的数组元素向左或向右旋转，以获得最大的答案。对于这个问题，我们将提供完整的代码和详细的解释。

问题介绍

在这个问题中，我们给定了一个数组，如果我们将所有元素与它们相应的索引号相乘，然后将所有元素的和相加，就会得到一个数字。通过一次旋转，我们可以将最左边或最右边的元素移动到数组的相反侧，这会导致每个元素的索引发生变化，我们可以对数组进行任意次数的旋转（但在旋转次数等于数组长度之后，我们将得到与第一个相同的数组），通过旋转数组，我们可以改变元素的索引，从而改变i*arr[i]的和。

We will try to maximize the sum with two approaches, first, let us see the example −

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

We can see that on the first rotation, we are getting the highest sum which is the 29.

方法

有两种方法可以实现找到所需的和，让我们看看它们两个 -

方法一是天真的方法，我们将在O(N)的时间内找到数组的所有旋转，并对每个旋转，我们将在O(N)的时间内通过遍历数组找到所有元素的和，而不使用任何额外的空间。

Example

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

时间复杂度和空间复杂度

The time complexity of the above code is O(N*N) where N is the size of the array and the space complexity of the above code is O(1).

At each iteration, we have only a difference of a single factor for the last element only because its factor will be updated from array length - 1 to 0 for the other elements their one more factor will be added. So we can write code as −

Example

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

时间复杂度和空间复杂度

The time complexity of the above code is O(N), where N is the size of the array and the space complexity of the above code is O(1). This approach is very better as compared to the previous one.