Python 46ms beats 94% with O(n)


  • 0
    E

    Let's change an angle:we fix A and rotate 0,1...n-1:

    F1=   X2+2X3+3X4+...+(n-1)Xn
    F2=X1+2X2+3X3+... (n-1)X(n-1)
    F3=2X1+3X2+...(n-1)X(n-2)+Xn
    ...
    so,Fk-F(k-1)=-(X1+X2+..+Xn)+n*X(n-k+!)
    

    so my solution is:

    def maxRotateFunction(self, A):
        s,l,s0=0,len(A),0
        for i in range(l):s0,s=s0+i*A[i],s+A[i]
        m=s0
        for n in A[-1:0:-1]:
            s0=s0+s-l*n
            if m<s0:m=s0
        return m
    

Log in to reply
 

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