JavaScript program to find the maximum sum of i*arr among all rotations of a given array

In this article, we will implement a JavaScript program to find the maximum sum of i*arr[i] among all rotations of a given array. Here i*arr[i] means that we want to maximize the sum of all elements of the array by multiplying them with the element at the current position. We can rotate the given array elements to the left or right to get the maximum answer. For this question, we will provide complete code and detailed explanation.

Problem introduction

In this question, we are given an array, if we multiply all elements with their corresponding index numbers and then add the sum of all elements, we will get a number. With one rotation, we can move the leftmost or rightmost element to the opposite side of the array, which causes the index of each element to change, and we can rotate the array any number of times (but after the number of rotations is equal to the length of the array , we will get the same array as the first one), by rotating the array we can change the index of the elements and thus the sum of 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.

method

There are two ways to achieve finding the required sum, let's look at both of them -

Method one is the naive approach, we will find all rotations of the array in O(N) time, and for each rotation, we will find the sum of all elements in O(N) time by traversing the array , without using any extra space.

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)

Time complexity and space complexity

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)

Time complexity and space complexity

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.

Conclusion

In this tutorial, we implemented a JavaScript program to find the maximum sum of i*arr[i] among all rotations of a given array. We saw two methods, one is to find all rotations of a given array and then compare the results of their i*arr[i] expressions. In the second method, we reduce the time complexity from O(N*N) to O(N) by using mathematical methods.

The above is the detailed content of JavaScript program to find the maximum sum of i*arr among all rotations of a given array. For more information, please follow other related articles on the PHP Chinese website!