इस समस्या में, हमें n तत्वों से युक्त एक array 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 बार घुमाना है। प्रत्येक घुमाव के बाद, हम योग (i*arr[i]) पाएंगे और सभी मानों का अधिकतम मान लौटाएंगे। यह बहुत अच्छा है लेकिन समय जटिलता ओ (एन 2) के क्रम की है। समस्या का एक अधिक कुशल समाधान है योग (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),
. का उपयोग करके sum(k) का मान ज्ञात कर सकते हैंअब, समाधान में हम सरणी के सभी मानों का योग पाएंगे, फिर योग (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