C++ এ অনুমোদিত প্রদত্ত অ্যারেতে শুধুমাত্র ঘূর্ণন সহ Sum(i*arr[i]) এর সর্বোচ্চ মান খুঁজুন

এই সমস্যায়, আমাদেরকে n উপাদান সমন্বিত একটি অ্যারে অ্যারে [] দেওয়া হয়েছে। আমাদের সমষ্টির সর্বাধিক মান (i*arr[i]) খুঁজে বের করতে হবে শুধুমাত্র প্রদত্ত অ্যারেতে ঘূর্ণন সহ। (i*arr[i]) এর সর্বাধিক যোগফল খুঁজে বের করার জন্য, আমরা যেকোনো সংখ্যক ঘূর্ণন সম্পাদন করতে পারি।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

arr[] = {4, 1, 3, 7, 2}

আউটপুট

43

ব্যাখ্যা

সর্বোচ্চ মান পেতে আমরা অ্যারেটিকে একবার ঘোরাব, ঘূর্ণনের পরে অ্যারে হবে {2, 4, 1, 3, 7}

যোগফল =0*2 + 1*4 + 2*1 + 3*3 + 4*7 =0 + 4 + 2 + 9 + 28 =43

সমাধান পদ্ধতি

সমস্যার একটি সহজ সমাধান হল অ্যারে এন বার ঘোরানো। প্রতিটি রোটেশনের পরে, আমরা যোগফল (i*arr[i]) খুঁজে পাব এবং সমস্ত মানগুলির সর্বাধিক প্রদান করব। এটি দুর্দান্ত তবে সময়ের জটিলতাটি অর্ডার O(n2) এর। সূত্র ব্যবহার করে ঘূর্ণন ছাড়া যোগফলের মান (i*arr[i]) খুঁজে বের করা সমস্যার একটি আরও কার্যকরী সমাধান।

আসুন গাণিতিকভাবে সূত্রটি বের করি,

Let the sum after k rotation is equal to sum(k).
sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1

এখন, আমরা সেই মানগুলিকে ঘোরাব যার পরে যোগফল হবে,

sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1
sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]
sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]

একইভাবে যোগফল(2) - যোগফল(1),

sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]

সমীকরণ সাধারণীকরণ,

sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]

এটি ব্যবহার করে আমরা sum(0),

এখন, সমাধানটিতে আমরা অ্যারের সমস্ত মানের যোগফল খুঁজে পাব, তারপর যোগফল(0) এর মানটি বের করব। একটি লুপ ব্যবহার করে, আমরা 1 থেকে n পর্যন্ত যোগফল(k) এর সমস্ত মান খুঁজে পাব। এবং তাদের সর্বাধিক ফেরত দিন।

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

উদাহরণ

#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
   int arrSum = 0;
   int currSum = 0;
   for (int i=0; i<n; i++){
      arrSum = arrSum + arr[i];
      currSum = currSum+(i*arr[i]);
   }
   int maxSum = currSum;
   for (int j=1; j<n; j++){
      currSum = currSum + arrSum-n*arr[n-j];
      if (currSum > maxSum)
         maxSum = currSum;
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 1, 3, 7, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
   return 0;
}

আউটপুট

The maximum value of sum(i*arr[i]) using rotations is 43