极客笔记JavaScript 在给定数组的所有旋转中找到i*arr[i]的最大和
在本文中，我们将实现JavaScript程序，用于在给定数组的所有旋转中找到iarr[i]的最大和。这里的iarr[i]表示我们通过将数组的所有元素与当前位置的元素乘积相乘，以最大化数组所有元素的和。我们可以将给定数组的元素向左或向右旋转位置，以获得最大的答案。对于这个问题，我们将看到完整的代码和详细的解释。
问题介绍
在这个问题中，我们有一个数组，如果我们将所有元素乘以它们各自的索引号，然后将它们的总和取出来，会得到一个数字。通过一次旋转，我们可以将最左边或最右边的元素移动到数组的相反位置，这导致改变每个元素的索引，并且我们可以任意次数地应用这种旋转（但在旋转次数等于数组长度之后，我们会得到与第一个相同的数组），通过旋转数组，我们可以改变元素的索引，从而改变i*arr[i]的和。
我们将尝试用两种方法最大化这个和，首先，让我们看一个示例 −
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
我们可以看到，在第一次旋转中，我们得到的最大和是29。
方法
有两种方法可以用来找到所需的和，我们来看看它们：
方法一是朴素方法，我们将在O(N)的时间内找到数组的所有旋转，并对每个旋转遍历数组以找到所有元素的和，不使用任何额外的空间。
示例
// 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)
时间和空间复杂度
上述代码的时间复杂度是O(N*N)，其中N是数组的大小，而上述代码的空间复杂度是O(1)。
在每次迭代中，只有最后一个元素有一个因子的差异，因为其因子将从数组长度-1更新为0，而其他元素将增加一个因子。因此，可以将代码写为-
示例
// 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)
时间和空间复杂度
以上代码的时间复杂度为O(N)，其中N是数组的大小，上述代码的空间复杂度为O(1)。与前一个方法相比，这种方法要好得多。
结论
在本教程中，我们已经实现了JavaScript程序，用于找出给定数组的所有旋转中的i*arr[i]的最大和。我们已经看到了两种方法，一种是找出给定数组的所有旋转，然后比较它们的结果来得到表达式i*arr[i]。在第二种方法中，我们使用了数学方法，将时间复杂度由O(N*N)降低到了O(N)。