6 Lines Python O(n) Solution (53ms)


  • 0

    Main idea: use F(n) to get F(n+1)

    In the provided Example:
    A = [4, 3, 2, 6]
    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
    ...

    By observation, F(n+1) is actually F(n) + sum(A) - len(A)xA[-(n+1)].

    In the above case: sum(A) = 4+3+2+6 = 15, index = -1
    F(1) = F(0) + sum(A) - len(A)*A[index] = 25 + 15 - 4x6 = 16

    Therefore, we just need to move the index backward iteratively.
    Put everything into a for loop, work done.

    class Solution(object):
        def maxRotateFunction(self, A):
            if not A: return 0
            maxres = tmp = sum([i*A[i] for i in xrange(len(A))])
            tot, index = sum(A), -1
            for index in xrange(-1, -len(A)-1, -1):
                maxres, tmp = max(maxres, tmp), tmp+tot-(len(A)*A[index])
            return maxres
    

Log in to reply
 

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