6-liner O(N) time, O(1) space


  • 0

    F[k] has recursion:

    F[k] = F[k-1] + sum(A) - n*A[n-k]    for 0 < k < n = A.size()
    
    int maxRotateFunction(vector<int>& A) 
    {
        int n = A.size(), sum = 0, res = 0;
        for (int i = 0; i < n; ++i) 
            res += i*A[i], sum += A[i]; // initialize res as F[0]
        
        for (int i = n-1, F = res; i >= 1; --i)
            res = max(res, F += (sum-n*A[i]));
        return res;
    }

Log in to reply
 

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