text: Instead of using some DP methodology to solve the problem, I have a very intuitive way to approach the solution.
  Think about the machine
  i, after we make all machines have the same dresses, how many dresses will be passed through machine
  i?
  Let's denote the current sum of dresses of machines
  [0...i-1] as
  leftSums[i], and the current sum of dresses of machines
  [i+1...n-1] as rightSums[i].
  Let's denote the expected sum of dresses of machines
  [0...i-1] as
  expLeft, which means after all dresses are equally distributed, the sum of address in machines
  [0...i-1] should be
  expLeft. The same logic applies to machines
  [i+1...n-1], denoted as
  expRight.
  Then the above question should be clearly answered. If
  expLeft is larger than
  leftSums[i], that means no matter how you move the dresses, there will be at least
  expLeft - leftSums[i] dresses being moved to left of machine
  i, which means pass through machine
  i. For the right machines of machine i, the logic remains the same. So we could conclude that the minimum dresses passed through machine
  i will be:
  left = expLeft > leftSums[i] ? expLeft - leftSums[i] : 0; right = expRight > rightSums[i] ? expRight - rightSums[i] : 0; total = left + right;
  With this answer in mind, we could know that the minimum moves is the maximum dresses that pass through for each single machine, because for each dress, it will require at least one move. Hence the following solution. The code could be more concise, but I will leave it here for purpose of explanation.
  If you have any doubts or suggestions for this solution, any comments are welcome.
  public class Solution { public int findMinMoves(int[] machines) { int n = machines.length; int sum = 0; for (int num : machines) { sum += num; } if (sum % n != 0) { return -1; } int avg = sum / n; int[] leftSums = new int[n]; int[] rightSums = new int[n]; for (int i = 1; i < n; i ++) { leftSums[i] = leftSums[i-1] + machines[i-1]; } for (int i = n - 2; i >= 0; i --) { rightSums[i] = rightSums[i+1] + machines[i+1]; } int move = 0; for (int i = 0; i < n; i ++) { int expLeft = i * avg; int expRight = (n - i - 1) * avg; int left = 0; int right = 0; if (expLeft > leftSums[i]) { left = expLeft - leftSums[i]; } if (expRight > rightSums[i]) { right = expRight - rightSums[i]; } move = Math.max(move, left + right); } return move; } }
  @mgispk
  It's great to see someone has the idea with me. To be honest, I'm still not very clear about the DP solution, and this one looks more intuitive to me.
  I used one array to record the 'flow' of dress from each machine to each direction. + means moving left while - means moving right.
  The problem description states n can be as large as 1e5 and dress can be 1e5 too. In this case we may have sum up to 1e10 which is greater than 2^31 - 1. So I use Long to compute everything, but looks like the test case doesn't cover it.
  Here's my solution.
  public class Solution { public int findMinMoves(int[] machines) { if(machines == null || machines.length == 0) return 0; long sum = 0; int n = machines.length; for(int m : machines) sum += m; if(sum % n != 0) return -1; long ave = sum / n; sum = 0; long[] flow = new long[n - 1]; // For n machines, there're n - 1 slots in between. So we compute the flow of dress. // Positive means dress move to left, while negative right. for(int i = 0; i < n - 1; i++) { sum += machines[i]; flow[i] = ave * (i + 1) - sum; } long res = 0; for(int i = 0; i < n; i++) { long left = i == 0 ? 0 : flow[i - 1]; long right = i == n - 1 ? 0 : flow[i]; // Below three IF conditions may not be needed, but it's good to show the idea. if(left > 0) res = Math.max(res, left); if(right < 0) res = Math.max(res, -right); // If there's dress flow out of current machine to both left and right, we need to // add them because only one dress can be moved at one time. if(left > 0 && right < 0) res = Math.max(res, left - right); } return (int)res; } }
  @seeker_13 Nice catch for the overflow problem.
  Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.