Share my C++ solution with explanation, easy to understand


  • 2
    V

    F(0) = 0*A[0] + 1*A[1] + ...... + (n-1)*A[n-1]
    F(1) = 0 *A[n-1] + 1*A[0] + 2*A[1] + 3*A[2] + ...... + (n-1)*A[n-2]
    .
    .
    F(n-1) = 0*A[1] + 1*A[2] + 2*A[3] + ...... + (n-1)*A[0]
    F(1) - F(0) = A[0] + A[1] + A[2] + ...... + A[n-2] - (n-1)*A[n-1]
    ==>F(1) = (A[0] + A[1] + A[2] + ...... + A[n-1]) - n*A[n-1] + F(0)
    set sum = A[0] + A[1] + A[2] + ...... + A[n-1]
    F(2) = sum - n*A[n-2] + F(1)
    .
    .
    F(i) = sum - n*A[n-i] + F(i-1)


    class Solution {
    public:
        int maxRotateFunction(vector<int>& A) {
            int n = A.size();
            int ret = 0;
            int sum = 0;
            int f = 0;
            
            for (int i = 0; i < n; i++)
            {
                sum += A[i];
                f += i * A[i];
            }
            
            ret = f;
            for (int i = 1; i < n; i++)
            {
                f = f + sum - n * A[n - i];
                ret = max(ret, f);
            }
            
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.