C++ में रोटेट फंक्शन

मान लीजिए हमारे पास पूर्णांकों की एक सरणी A दी गई है और मान लें n सरणी A की लंबाई है। अब मान लें Bk सरणी A को k पोजीशन क्लॉक-वाइज घुमाकर प्राप्त की गई सरणी है। यहां रोटेशन को निम्नानुसार परिभाषित किया जा सकता है:

• F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

अब F(0), F(1), ..., F(n-1) का अधिकतम मान ढूंढें।

उदाहरण के लिए, यदि इनपुट A = [4,3,2,6] जैसा है, तो:

• F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
• F(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 के दो सरणी बनाएं, ये right और left हैं
• left[0] := A[0]
• i को 1 से n - 1 तक लूप करें
  • left[i] := left[i] + left[i - 1]
  • left[i] := left[i] + A[i]
• right[n - 1] := A[n - 1]
• i को n - 1 से 0 तक लूप करें
  • right[i] := right[i] + right[i + 1]
  • right[i] := right[i] + A[i]
• rightMul := 0, cnt := n - 1
• i को n - 1 से 1 तक लूप करें
  • rightMul := rightMul + A[i] * cnt
  • cnt को 1 से घटाएं
• आकार n की एक सरणी x बनाएं
• i को 0 से n - 2 तक लूप करें
  • x[i] := rightMul
  • rightMul := rightMul - right[i + 1]
• leftMul := 0, cnt := 1
• i को 0 से n - 2 तक लूप करें
  • leftMul := leftMul + A[i] * cnt
  • cnt को 1 से बढ़ाएं
• cnt को 1 से घटाएं
• i को n - 1 से 1 तक लूप करें
  • x[i] := x[i] + leftMul
  • leftMul := leftMul - A[i - 1] * cnt
  • यदि i - 2 >= 0, तो leftMul := leftMul + left[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