C++-এ রোটেট ফাংশন

একটি পূর্ণসংখ্যা অ্যারে A দেওয়া আছে, দৈর্ঘ্য n। 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 = 25
• F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16
• F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 23
• F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 26

সমাধানের ধাপগুলো:

• n := A.size(), যদি n == 0, ০ ফেরত দিন।
• ret := 0, আকার n-এর দুটি অ্যারে right আর left।
• left[0] := A[0]
• i = 1 থেকে n-1: left[i] += left[i-1]; left[i] += A[i]
• right[n-1] := A[n-1]
• i = n-2 থেকে 0: right[i] += right[i+1]; right[i] += A[i]
• rightMul := 0, cnt := n-1
• i = n-1 থেকে 1: rightMul += A[i]*cnt; cnt--
• x আকার n-এর অ্যারে।
• i = 0 থেকে n-2: x[i] = rightMul; rightMul -= right[i+1]
• leftMul := 0, cnt := 1
• i = 0 থেকে n-2: leftMul += A[i]*cnt; cnt++
• cnt--
• i = n-1 থেকে 1:
  • x[i] += leftMul
  • leftMul -= A[i-1]*cnt
  • যদি i-2 >= 0, 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