ผลรวมสูงสุดของ i * arr[i] จากการหมุนทั้งหมดของอาร์เรย์ที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr งานของเราคือสร้างโปรแกรมที่จะหาผลรวมสูงสุดของ i*arr[i] จากการหมุนทั้งหมดของอาร์เรย์ที่กำหนดใน C++

คำอธิบายโปรแกรม − ที่นี่ เราจะหาผลรวมสูงสุดของผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์คูณด้วยดัชนี {i * arr[i]} ในการหมุน

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − array arr ={4, 8, 1, 5}

ผลผลิต − 37

คำอธิบาย −

All rotations with the sum of i*arr[i] :
{4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25
{8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23
{1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37
{5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23
The max sum of i*arr[i] is for third rotation.

วิธีแก้ปัญหาง่ายๆ นี้คือการคำนวณผลรวมขององค์ประกอบทั้งหมดคูณด้วยดัชนีของการหมุนแต่ละครั้ง แล้วหาผลรวมสูงสุดของการหมุนทั้งหมด สำหรับสิ่งนี้ เราจะหมุนอาร์เรย์ n ครั้งและคำนวณผลรวมสำหรับแต่ละรายการและเก็บผลรวมของตัวแปร maxSum หากผลรวมของการหมุนปัจจุบันมากกว่าค่าสุดท้าย

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันนี้

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
return b;
}
int calculateMaxSum(int arr[], int n){
   int maxSum = 0, sum = 0;
   for (int i=0; i<n; i++){
      sum = 0;
      for (int j=0; j<n; j++){
         int index = (i+j)%n;
         sum += j*arr[index];
      }
      maxSum = findMax(maxSum, sum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

ผลลัพธ์

The maximum sum of all the rotation of the array is 37

วิธีแก้ปัญหาที่มีประสิทธิภาพคือใช้การคำนวณผลรวมของการหมุนรอบถัดไปโดยใช้การหมุนครั้งก่อน เราจะใช้สูตร

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1]*(n-1)

เมื่อใช้สูตรนี้ เราจะพบ nextSum และที่ส่วนท้ายของ loop body เราจะตรวจสอบว่า nextSum มีค่ามากกว่า maxSum หรือไม่ ถ้าใช่ maxSum =nextSum

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันนี้

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calculateMaxSum(int arr[], int n){
   int arraySum = 0, currentSum = 0, nextSum ;
   for (int i=0; i<n; i++){
      arraySum += arr[i];
      currentSum += i*arr[i];
   }
   int maxSum = currentSum;
   for (int i=1; i<n; i++){
      nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n1);
      currentSum = nextSum;
      maxSum = findMax(maxSum, nextSum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

ผลลัพธ์

The maximum sum of all the rotation of the array is 37