仅允许旋转给定数组的情况下，查找Sum(i*arr[i])的最大值JavaScript程序

我们将使用一种数学方法来查找数组中元素的索引和值的乘积之和的最大值。通过旋转数组，我们可以通过将数组的最大值放在乘积最大的索引处来最大化此和。我们将使用的算法包括查找索引和元素值的乘积之和，然后将此和与数组长度和索引值之和的乘积之间的差添加到此和。

将来，我们将不断地将此算法应用于不同的数组，以查找仅允许旋转的情况下元素的索引和值的乘积之和的最大值。此解决方案效率很高，因为它只需要遍历数组一次，时间复杂度为 O(n)。使用此算法，我们可以快速轻松地找到数组中元素的索引和值的乘积之和的最大值。

方法

  • 所有旋转的总和可以通过将数组中每个元素与其对应的索引相乘并将结果相加来获得。

  • 可以通过找到具有最大值的索引并将数组旋转使得最大值成为第一个元素来获得最大值。

  • 可以通过将每个元素的值与其索引相乘并将结果与当前最大值进行比较来找到最大值。

  • 所有旋转的总和可以通过将所有旋转的总和添加到当前总和并除以旋转次数来找到。

  • 最大值可以作为结果返回。

示例

该问题可以通过首先找到数组中所有元素的总和，然后迭代地旋转数组并通过将当前旋转的差值添加到之前的总和来更新总和来解决。最大和将是答案。这是一个完整的 JavaScript 示例：

function maxSum(arr) {
   let n = arr.length;
   let arrSum = 0;
   let currVal = 0;
   for (let i = 0; i < n; i++) {
      arrSum += arr[i];
      currVal += i * arr[i];
   }
   let maxVal = currVal;
   for (let j = 1; j < n; j++) {
      currVal = currVal + arrSum - n * arr[n - j];
      maxVal = Math.max(maxVal, currVal);
   }
   return maxVal;
}
let arr = [1, 20, 2, 10];
console.log(maxSum(arr)); // Output: 72

解释

  • 函数maxSum接收一个数组作为输入，并返回通过旋转数组并对每个旋转取i * arr[i]的和可以获得的最大和。

  • 变量n存储数组的长度。

  • 变量arrSum存储数组中所有元素的总和，并初始化为 0。

  • 变量currVal存储当前旋转的i * arr[i]的和，并初始化为 0。

  • 第一个循环计算数组中所有元素的总和以及第一次旋转的i * arr[i]的和。

  • 变量maxVal存储最大和，并初始化为currVal。

  • 第二个循环迭代地旋转数组并更新每次旋转的i * arr[i]的和。当前旋转的i * arr[i]的和通过将当前旋转的差值添加到之前的总和来更新。

  • currVal的值通过添加当前旋转的i * arr[i]的和与前一次旋转的i * arr[i]的和之间的差值来更新。该差值是通过从arrSum中减去n * arr[n - j]来计算的。

  • 使用Math.max函数将每次旋转的currVal的最大值存储在maxVal中。

  • 最后，返回maxVal的值作为答案。

更新于：2023年3月15日

浏览量：301

开启你的职业生涯

完成课程获得认证

开始学习
广告