Xoay hàm trong C ++

Giả sử chúng ta đã Cho một mảng các số nguyên A và gọi n là độ dài của mảng A. Bây giờ giả sử Bk là một mảng thu được bằng cách xoay mảng A, k vị trí theo đồng hồ. Ở đây, vòng quay có thể được định nghĩa là -

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

Bây giờ, hãy tìm giá trị lớn nhất của F (0), F (1), ..., F (n-1).

Vì vậy, nếu đầu vào là A =[4,3,2,6], thì -

• 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

Tối đa là 26.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng A, nếu n là 0 thì trả về 0

• ret:=0, tạo hai mảng có kích thước n, hai mảng này là bên phải và bên trái

• trái [0]:=A [0]

• cho tôi trong phạm vi từ 1 đến n - 1

  • left [i]:=left [i] + left [i - 1]

  • left [i]:=left [i] + A [i]

• right [n - 1]:=A [n - 1]

• đối với tôi trong phạm vi n - 1 xuống 0

  • right [i]:=right [i] + right [i + 1]

  • right [i]:=right [i] + A [i]

• rightMul:=0, cnt:=n - 1

• đối với tôi trong phạm vi n - 1 xuống 1

  • rightMul:=rightMul + A [i] * cnt

  • giảm cnt đi 1

• Tạo một mảng x có kích thước n

• cho tôi trong phạm vi từ 0 đến n - 2

  • x [i]:=rightMul

  • rightMul:=rightMul - right [i + 1]

• leftMul:=0, cnt:=1

• đối với tôi trong phạm vi 0 xuống đến n - 2

  • leftMul:=leftMul + A [i] * cnt

  • tăng cnt lên 1

• giảm cnt đi 1

• đối với tôi trong phạm vi n - 1 xuống 1

  • x [i]:=x [i] + leftMul

  • leftMul:=leftMul - A [i - 1] * cnt

  • if i - 2> =0, then leftMul:=leftMul + left [i - 2]

• trả về tối đa của x

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[4,3,2,6]

Đầu ra

26