public class Solution {
public int findMinMoves(int[] machines) {
int total = 0, target = 0, result = 0, n = machines.length;
for (int d : machines) total += d;
if (total == 0) return 0;
if (total % n != 0) return 1;
target = total / n;
int[] move = new int[n];
for (int i = 0; i < n  1; i++) {
if (machines[i] > target) {
move[i] += machines[i]  target;
machines[i + 1] += machines[i]  target;
machines[i] = target;
result = Math.max(result, move[i]);
}
else {
move[i + 1] = target  machines[i];
machines[i + 1] = target  machines[i];
machines[i] = target;
result = Math.max(result, move[i + 1]);
}
}
return result;
}
}
Java O(n) DP Solution


@shawngao Thank you for your solution! I am doubled why you call it by Dynamic Programming. This problem is difiicult for me since I find it hard to abstract to a model or algorithm I am familiar with. I will appreciate if you could explain more

@victorzhang21503 I think he is trying to find the peak who give the most items to two side, which is equal to the maximum movement.

I appreciate this nice and clean code. I was first attracted by "DP" in the topic. However, it's not DP. It's more like a deduction rather than optimal substructure.
One insight I want to add:
You could consider this problem as a pipeline, and the bandwidth of pipeline is "1". From the leftist machine to the right, the water flows in / out. To get the balanced state, calculate how many times you need to use this pipeline.