Rotate Function

这题用了一个很巧妙的RabinKarp式思维，主要在于观察每一次的rotate，真正变化的地方分两处，一处除最后一个数之外其他所有元素都加了一个本身，而最后一个元素的积全部清零，所以实际上要做的就是找出数组的和，每次rotate只要加上这个和再减去当前rotate这一轮需要被清零的的值就可以了

class Solution(object):
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0

        cumSum = sum(A)
        n = len(A)
        product = reduce(operator.add, map(lambda x, y: x * y, range(n), A))

        result = product
        for i in xrange(1, n):
            product = product + cumSum - n * A[n - i]
            result = max(result, product)
        return result