मान लीजिए कि हमने पूर्णांक A की एक सरणी दी है और n सरणी A की लंबाई है। अब मान लें कि Bk सरणी A को घुमाकर प्राप्त की गई एक सरणी है, k स्थिति घड़ी-वार। यहां रोटेशन को −
. के रूप में परिभाषित किया जा सकता है-
एफ (के) =0 * बीके [0] + 1 * बीके [1] + ... + (एन -1) * बीके [एन -1]।
अब F(0), F(1), ..., F(n-1) का अधिकतम मान ज्ञात कीजिए।
तो अगर इनपुट ए =[4,3,2,6] जैसा है, तो -
-
एफ(0) =(0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) =0 + 3 + 4 + 18 =25
-
एफ(1) =(0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) =0 + 4 + 6 + 6 =16
-
F(2) =(0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) =0 + 6 + 8 + 9 =23
-
F(3) =(0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) =0 + 2 + 12 + 12 =26
अधिकतम 26 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=सरणी A का आकार, यदि n 0 है, तो वापस 0
-
ret :=0, आकार n के दो सरणियाँ बनाएँ, ये दाएँ और बाएँ हैं
-
बाएं [0] :=ए[0]
-
मैं के लिए 1 से n - 1 की सीमा में
-
बाएँ [i] :=बाएँ[i] + बाएँ[i – 1]
-
बाएँ [i] :=बाएँ[i] + A[i]
-
-
दाएं [एन -1]:=ए [एन -1]
-
मैं के लिए n - 1 से 0 तक की श्रेणी में हूं
-
दाएँ [i] :=दाएँ[i] + दाएँ[i + 1]
-
दाएँ [i] :=दाएँ[i] + A[i]
-
-
राइटमुल:=0, सीएनटी:=n – 1
-
मेरे लिए n - 1 से नीचे 1 तक की श्रेणी में है
-
राइटमुल:=राइटमुल + ए [i] * सीएनटी
-
1 से कम करें
-
-
n आकार की एक सरणी x बनाएं
-
मैं के लिए 0 से n - 2 की सीमा में
-
x[i] :=rightMul
-
राइटमुल:=राइटमुल - राइट [i + 1]
-
-
लेफ्टमूल:=0, सीएनटी:=1
-
मैं के लिए 0 से नीचे n - 2 की सीमा में
-
लेफ्टमूल:=लेफ्टमूल + ए [i] * सीएनटी
-
cnt को 1 से बढ़ाएँ
-
-
1 से कम करें
-
मेरे लिए n - 1 से नीचे 1 तक की श्रेणी में है
-
x[i] :=x[i] + leftMul
-
लेफ्टमुल:=लेफ्टमूल - ए [i - 1] * सीएनटी
-
अगर मैं – 2>=0, फिर लेफ्टमूल :=लेफ्टमूल + लेफ्ट [i – 2]
-
-
अधिकतम x
. लौटाएं
उदाहरण (C++)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxRotateFunction(vector<int>& A) {
lli n = A.size();
if(n == 0) return 0;
lli ret = 0;
vector <lli>right(n);
vector <lli> left(n);
left[0] = A[0];
for(lli i = 1; i < n; i++){
left[i] += left[i - 1];
left[i] += A[i];
}
right[n - 1] = A[n - 1];
for(lli i = n - 2; i >= 0; i--){
right[i] += right[i + 1];
right[i] += A[i];
}
lli rightMul = 0;
lli cnt = n - 1;
for(lli i = n - 1; i > 0; i--){
rightMul += (A[i] * cnt);
cnt--;
}
vector <lli> x(n);
for(lli i = 0; i < n - 1; i++){
x[i] = rightMul;
rightMul -= right[i + 1];
}
lli leftMul = 0;
cnt = 1;
for(lli i = 0; i < n - 1; i++){
leftMul += A[i] * cnt;
cnt++;
}
cnt--;
for(lli i = n - 1; i >= 1; i--){
x[i] += leftMul;
leftMul -= (A[i - 1] * cnt);
if(i - 2 >= 0) leftMul += left[i - 2];
}
ret = INT_MIN;
for(lli i = 0; i < x.size(); i++) ret = max(ret, x[i]);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {4,3,2,6};
cout <<(ob.maxRotateFunction(v));
} इनपुट
[4,3,2,6]
आउटपुट
26