数学方法

algorithm

旋转函数(Rotate Function)

• 旋转函数最大值
  

  $$A=[a_0,a_1,a_2,\cdots a_{n-1}] \\ B_0 = [a_0,a_1,a_2,\cdots a_{n-1}]\\ B_1 = [a_{n-1},a_0,a_1,\cdots a_{n-2}]\\ B_k = [a_{n-k},a_{n-k+1},\cdots a_{n-k-1}]\\ F_0 = 0 * B_0[0] + 1 * B_0[1] + ... + (n-1) * B_0[n-1]\\ F_0 = [0,1,2,\cdots n-1]*\begin{bmatrix} a_0\\ a_1 \\ a_2\\ \vdots\\ a_n \end{bmatrix}=[a_0,a_1,\cdots a_n]*\begin{bmatrix} 0\\ 1 \\ 2\\ \vdots\\ n \end{bmatrix}\\ F_1 = [n-1,0,1,2,\cdots n-2]*\begin{bmatrix} a_0\\ a_1 \\ a_2\\ \vdots\\ a_n \end{bmatrix}\\ =[a_0,a_1,\cdots a_n]*\begin{bmatrix} n-1\\ 0\\ 1 \\ 2\\ \vdots\\ n-2 \end{bmatrix}\\ F_k = [n-k,n-k+1,\cdots,n-1,0,1,\cdots n-k-1]*\begin{bmatrix} a_0\\ a_1 \\ a_2\\ \vdots\\ a_n \end{bmatrix}=[a_0,a_1,\cdots a_n]*\begin{bmatrix} n-k\\ n-k+1\\ \vdots \\ n-1\\ 0,\\ \vdots\\ n-k-1 \end{bmatrix}\\ F_{k} - F_{k-1} = [a_0,a_1,\cdots,a_k,\cdots, a_n]*\begin{bmatrix} (n-k) - (n-k-1)\\ (n-k+1) - (n-k)\\ (n-k+2) - (n-k+1)\\ \vdots\\ 0 - (n-1)\\ 1 - 0\\ \vdots\\ (n-k-1) - (n-k-2) \end{bmatrix}\\ =[a_0,a_1,\cdots,a_k,\cdots, a_n]*\begin{bmatrix} 1\\ 1\\ 1\\ \vdots\\ 1 - n\\ 1\\ \vdots\\ 1 \end{bmatrix}\\ = \sum_{i=1}^{n-1}a_i - n*a_k\\ F_k = F_{k-1} + \sum_{i=1}^{n-1}a_i - n*a_k$$

• 依据递推公式$F_k = F_{k-1} + \sum_{i=1}^{n-1}a_i - n*a_k$

 int maxRotateFunction(vector<int>& A) {
        int n = A.size();
        long maxv = 0;
        long sum = 0;
        long f = 0;
        for(int i = 0; i < n; i++ ) {
            sum += A[i];
            long t = i;
            f += t * A[i];
        }
        maxv = f;
        for(int i = 1; i < n; i++ ) {
            long t = n;
            t *= A[n-i];
            f = f + sum - t;
            maxv = max(f,maxv);
        }
        return maxv;
    }