Super Washing Machines

此题其实道理非常不好讲，也不好证明，而且个人觉得是一个完全和DP无关的问题，一开始肯定会以为我们就是用这个最后的平均值去找开始跟它差距最大的那个数就是最后的结果，但是有一个test case推翻了这个方法[0,0,11,5]，而最后实际上应该怎么做呢？

首先求出这个平均值，然后将数组中的每个数都减去这个平均值，最后从一开始的位置开始逐个抹平高低差，如0，0，11，5这个数组就变成-4，-4，7，1，然后我们再遍历这个数组，同时用一个变量去记录当前的累积和，而我们需要的结果就是累积和中的绝对值最大值或者是单独元素的最大值，从这里其实很难看出有什么DP规律在里面，而是一个类似maximum subarray的做法去找结果，不过此题最难的还是找到这个修改后数组的阶段

class Solution(object):
    def findMinMoves(self, machines):
        """
        :type machines: List[int]
        :rtype: int
        """
        total = sum(machines)
        n = len(machines)
        if total % n:
            return -1

        avg = total / n
        machines = map(lambda x: x - avg, machines)
        result = 0
        tmp = 0
        for i in xrange(n - 1):
            tmp += machines[i]
            result = max(abs(tmp), result, machines[i])
        return result