517. Super Washing Machines

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n = machines.size(), sum = 0;
        for (int i = 0; i < n; i++) sum += machines[i];
        if (!sum) return 0;
        if (sum % n) return -1;
        int tar = sum / n;
        int res = 0;

        vector<int> moves(n, 0);
        for (int i = 0; i < n - 1; i++)
            if (machines[i] < tar) {    //move from i+1
                res = max(res, moves[i + 1] = tar - machines[i]);
                machines[i + 1] -= tar - machines[i];
                machines[i] = tar;  //いらないけど
            } else {    //move the spare dress to i+1
                res = max(res, moves[i] = moves[i] + machines[i] - tar); //attention!you need to add up the original moves[i], as (moves[i]) and (machines[i] - tar) are both dresses moved out from the ith machine
                machines[i + 1] += machines[i] - tar;
                machines[i] = tar;
            }

        return res;
    }
};

O(1)space

def findMinMoves(self, machines):
    if sum(machines) % len(machines) == 0:
        target = sum(machines) / len(machines)
    else:
        return -1
    toLeft = 0
    res = 0
    for i in range(len(machines)):
        toRight =  machines[i]- target - toLeft
        res = max(res, toLeft, toRight, toLeft + toRight)
        toLeft = -toRight
    return res