資料結構
網路
關係資料庫管理系統 (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 次瀏覽
