इस समस्या में, हमें एक सरणी arr दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में दी गई सरणी के सभी घुमावों (rotations) में i*arr[i] का अधिकतम योग ढूंढे।
प्रोग्राम विवरण - यहां, हम सभी घुमावों के योगों में से तत्वों को उनके सूचकांक {i * arr[i]} से गुणा करके अधिकतम योग ढूंढेंगे।
आइए एक उदाहरण से समझते हैं:
इनपुट - सरणी arr = {4, 8, 1, 5}
आउटपुट - 37
व्याख्या -
सभी घुमाव 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
तीसरे घुमाव के लिए i*arr[i] का अधिकतम योग है।
इस समस्या का एक सरल समाधान प्रत्येक घुमाव के सभी तत्वों को उनके सूचकांक से गुणा करके योग की गणना करना है। और फिर सभी घुमावों के योगों का अधिकतम ढूंढना। इसके लिए, हम सरणी को n बार घुमाएंगे और प्रत्येक के लिए योग की गणना करेंगे और यदि वर्तमान घुमाव का योग अंतिम से अधिक है तो maxSum वेरिएबल में संग्रहीत करेंगे।
उदाहरण
#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 << "सरणी के सभी घुमावों का अधिकतम योग है " << calculateMaxSum(arr, n);
return 0;
}
आउटपुट
सरणी के सभी घुमावों का अधिकतम योग है 37
एक कुशल समाधान पिछले घुमाव का उपयोग करके अगले घुमाव के योग की गणना करना है। हम सूत्र का उपयोग करेंगे:
nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1]*(n-1)
इस सूत्र का उपयोग करके, हम nextSum ढूंढेंगे और लूप बॉडी के अंत में, हम जांचेंगे कि क्या nextSum, maxSum से अधिक है, यदि हां तो 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] * (n-1);
currentSum = nextSum;
maxSum = findMax(maxSum, nextSum);
}
return maxSum;
}
int main(){
int arr[] = {4, 8, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "सरणी के सभी घुमावों का अधिकतम योग है " << calculateMaxSum(arr, n);
return 0;
}
आउटपुट
सरणी के सभी घुमावों का अधिकतम योग है 37
