इस समस्या में, हमें एक array arr दिया जाता है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो C++ में दिए गए ऐरे के सभी घुमावों के बीच i*arr[i] का अधिकतम योग प्राप्त करेगा।
कार्यक्रम विवरण - यहां, हम सरणी के सभी तत्वों के योग का अधिकतम योग उनके सूचकांक से गुणा करेंगे {i * arr[i]} रोटेशन में।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - सरणी गिरफ्तारी ={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 बार घुमाएंगे और प्रत्येक के लिए योगों की गणना करेंगे और यदि वर्तमान घुमाव का योग पिछले से अधिक है, तो अधिकतम योग चर का योग संग्रहीत करेंगे।
उदाहरण
इस समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
#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 पाएंगे और लूप बॉडी के अंत में, हम जांचेंगे कि क्या nextSum मैक्ससम से बड़ा है, यदि हां तो 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