JavaScript 程式求給定數組所有旋轉中 i*arr 的最大總和

在本文中，我們將實作JavaScript程序，用於找到給定陣列的所有旋轉中i*arr[i]的最大和。這裡的i*arr[i]表示我們要透過將它們與目前位置的元素相乘來最大化數組所有元素的和。我們可以將給定的陣列元素向左或向右旋轉，以獲得最大的答案。對於這個問題，我們將提供完整的程式碼和詳細的解釋。

問題介紹

在這個問題中，我們給定了一個數組，如果我們將所有元素與它們對應的索引號相乘，然後將所有元素的和相加，就會得到一個數字。透過一次旋轉，我們可以將最左邊或最右邊的元素移動到數組的相反側，這會導致每個元素的索引發生變化，我們可以對數組進行任意次數的旋轉（但在旋轉次數等於數組長度之後，我們將得到與第一個相同的數組），透過旋轉數組，我們可以改變元素的索引，從而改變i*arr[i]的和。

We will tr​​y 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.

方法

有兩種方法可以實現找到所需的和，讓我們看看它們兩個 -

方法一是天真的方法，我們將在O(N)的時間內找到數組的所有旋轉，並對每個旋轉，我們將在O(N)的時間內透過遍歷數組找到所有元素的和，而不使用任何額外的空間。

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)

時間複雜度與空間複雜度

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 can 法. 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)

時間複雜度與空間複雜度

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

在本教程中，我們實作了JavaScript程序，用於在給定數組的所有旋轉中找到i*arr[i]的最大和。我們看到了兩種方法，一種是找到給定數組的所有旋轉，然後比較它們的i*arr[i]表達式的結果。在第二種方法中，我們透過使用數學方法，將時間複雜度從O(N*N)降低到O(N)。

以上是JavaScript 程式求給定數組所有旋轉中 i*arr 的最大總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！