python solution beat 95% code with explanation


  • 0
    R

    First thought would be an N square solution;

    Then find out that
    f[0] = 0 * A[0] + 1 * A[1] + .... + (n-1) * A[n-1]
    f[1] = 1 * A[0] + 2 * A[1] + .... + (n-1) * A[n-2] + 0 * A[n-1] = f[0] + sum(A) - n * A[n-1]
    f[2] = 2 * A[0] + 3 * A[2] + ... + 0 * A[n-2] + 1 * A[n-1] = f[1] + sum(A) - n * A[n-2]
    .....
    Time complexity is O(n), space complexity is O(1)
    Here is the code:

    def maxRotateFunction(A):
            N = len(A)
            res = 0
            f = sum(A)
    
            for i in xrange(N):
                res += i * A[i]
    
            cur = res
            for i in xrange(1, N):
                cur = cur + f - N * A[N-i]
                res = max(res, cur)
            return res
    

Log in to reply
 

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