इस समस्या में, हमें n तत्वों वाली एक सरणी arr[] दी गई है। हमें केवल दी गई सरणी पर रोटेशन की अनुमति देकर Sum(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
समाधान दृष्टिकोण
समस्या का एक सरल समाधान सरणी को 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] => समीकरण 1
अब, हम मानों को घुमाएँगे जिसके बाद योग बन जाएगा,
sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => समीकरण 2 समीकरण 2 - समीकरण 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]
इसी तरह sum(2) - sum(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) का उपयोग करके sum(k) का मान खोज सकते हैं।
अब, समाधान में हम सरणी के सभी मानों का योग खोजेंगे, फिर sum(0) का मान खोजेंगे। एक लूप का उपयोग करके, हम 1 से n तक sum(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