数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定数组所有旋转中 i*arr[i] 的最大和的 JavaScript 程序
在本文中，我们将实现一个 JavaScript 程序，用于计算给定数组所有旋转中 i*arr[i] 的最大和。这里 i*arr[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) 时间内找到数组的所有旋转，并且对于每次旋转，它将在 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)。
166 次浏览
