এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে n সংখ্যক উপাদান থাকে। আমাদের শুধু রোটেশন ব্যবহার করে Sum(i*arr[i]) এর সর্বোচ্চ মান খুঁজে বের করতে হবে। সর্বোচ্চ সম পাওয়ার জন্য আমরা যেকোনো সংখ্যক রোটেশন করতে পারি।
উদাহরণ
ইনপুট
arr[] = {4, 1, 3, 7, 2}
আউটপুট
43
ব্যাখ্যা
আমরা একবার অ্যারে রোটেট করব সর্বোচ্চ মান পাওয়ার জন্য। রোটেশনের পর অ্যারে হবে {2, 4, 1, 3, 7}
Sum = 0*2 + 1*4 + 2*1 + 3*3 + 4*7 = 0 + 4 + 2 + 9 + 28 = 43
সমাধানের পদ্ধতি
একটি সহজ সমাধান হলো অ্যারে n বার রোটেট করা। প্রতিটি রোটেশনের পর sum(i*arr[i]) বের করে সবচেয়ে বড় মান ফেরত দেয়া। কিন্তু এর টাইম কমপ্লেক্সিটি O(n²)।
একটি আরও দক্ষ সমাধান হলো সূত্র ব্যবহার করে রোটেশন ছাড়াই sum(i*arr[i]) বের করা।
গাণিতিক সূত্র উদ্ভাবন
k রোটেশনের পর সম = sum(k) sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => সমীকরণ ১ একবার রোটেট করলে: sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => সমীকরণ ২ সমীকরণ ২ - সমীকরণ ১: sum(1) - sum(0) = arr[0] + arr[1] + ... arr[n-2] - (n-1)*arr[n-1] সামান্যীকরণ করলে: sum(k) - sum(k-1) = arr[0] + arr[1] + ... + arr[n-1] - n*arr[n-k]
এই সূত্র ব্যবহার করে sum(0) থেকে sum(k) বের করা যায়। সমাধানে আমরা প্রথমে অ্যারের সব উপাদানের যোগফল বের করব, তারপর sum(0) বের করব। লুপ চালিয়ে 1 থেকে n পর্যন্ত sum(k) বের করব এবং সর্বোচ্চ মান ফেরত দিব।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
int arrSum = 0;
int currSum = 0;
for (int i=0; i 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
