C++ এ প্রদত্ত অ্যারের সমস্ত ঘূর্ণনের মধ্যে i * arr[i] এর সর্বাধিক যোগফল

এই সমস্যায়, আমাদের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা C++ এ প্রদত্ত অ্যারের সমস্ত ঘূর্ণনের মধ্যে i*arr[i]-এর সর্বাধিক যোগফল খুঁজে পাবে।

প্রোগ্রামের বিবরণ − এখানে, আমরা ঘূর্ণনে তাদের সূচক {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 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