Python O(n), Math with explaination


  • 2
    C
    class Solution(object):
        def maxRotateFunction(self, A):
            sumA=sum(A)
            temp=0
            for i,c in enumerate(A):
                temp+=i*c
            maxx=temp
            for j in xrange(len(A)):
                temp+=(len(A)*A[j]-sumA)
                maxx=max(temp,maxx)
            return maxx
    

    First you get the temp by multiplyng each index and value. Then for each time you rotate index by clockwise, it's interesting to see the sum increases by len(A)A[j]-sum. And you just need to find the max one.
    For instance, you have INDEX of [0,1,2,3,4,5], next it changes to [5,0,1,2,3,4], the temp increases by 5
    first index's value i by 5*A[j] - the rest numbers' sum, which means the temp increses by 6(the length of A) * A[j] - the total number's sum. Because other numbers' index just "decreased" by one, expect the one whose "last" index was 0.


  • 0
    Z

    I think you code is really great.
    As I re-write with your idea, I got 100% beats. Thank you!

    class Solution(object):
        def maxRotateFunction(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            sumA, l = sum(A), len(A)
            temp_sum = sum([i * n for i, n in enumerate(A)])
            max_sum = temp_sum
            for v in A[:-1]:
                temp_sum = temp_sum -sumA + l * v
                if temp_sum > max_sum:
                    max_sum = temp_sum
            return max_sum
    

Log in to reply
 

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