# Java O(n) DP Solution

• ``````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;
}
}
``````

• @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 don't think this is DP solution

• 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.

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