I am working on a programming problem, and I'm having trouble with justifying, mathematically, the correctness of an algorithm.
The problem is
There are $n$ washing machines lined up in a row. Initially the $i$-th washing machine has $A_i$ dresses where $A_i \geq 0$. Assume 0-based indicing, so $i \in \{0, \ldots, n - 1\}$. Let $A$ denote the array of $A_i$. Also suppose that $\bar{a} = \frac{1}{n}\sum_{i=0}^{n-1}A_i$ is an integer. In one move, you can choose $m$ washing machines where $1 \leq m \leq n$ and pass one dress of each of the chosen washing machine to one of its adjacent washing machines at the same time. What is the minimum number of moves to ensure that all washing machines have the same number of dresses? Mathematically, the goal is to make all $A_i = \bar{a}$.
Let me illustrate with an example what we are trying to achieve. Suppose $A = [1,0,5]$. $\sum_i A_i = 6 \implies \bar{a} = 2$. So we want to make each $A_i = 2$. In one move we will change $[1,0,5]$ to $[1,1,4]$. In the next move we will change $[1,1,4]$ to $[2,1,3]$. In the 3rd and final move, we will change $[2,1,3]$ to $[2,2,2]$. The minimum number of moves is 3.
The algorithm is apparently to consider each position $i$ in the array, and look at the subarray to the left and to the right of position $i$. Physically, you want to consider each washing machine and consider how many dresses must pass through it.
For each subarray, we compute the sum of the elements in that subarray. e.g., if we're looking at position $i = 4$ and $n = 10$, then we compute the left subarray sum $L_i = \sum_{j=0}^{3} A_j$ and right subarray sum $R_i = \sum_{j = i = 4}^{n - 1} A_j$. Then if $\bar{a} * i > L_i$, that means we require exactly $f_i = \bar{a} * i - L_i$ dresses to pass through $A_i$ to $A_{i - 1}$. If $\bar{a} * (n - i - 1) > R_i$, that means we require exactly $g_i = \bar{a} * (n - i - 1) - R_i$ dresses to pass through $A_i$ to $A_{i + 1}$. And then, apparently the answer is
$$ \max_{i \in \{0, \ldots, n - 1\}}(\max(0,f_i) + \max(0, g_i)) $$
For the above example that we did, we see that when $i = 0$, we have $f_0, g_0 < 0$, so $\max(0,f_0) + \max(0, g_0) = 0$
When $i = 1$, we have $f_1 = 1$ and $g_1 < 0$, so $\max(0,f_1) + \max(0, g_1) = 1$
When $i = 2$, we have $f_2 = 3$ and $g_2 = 0$, so $\max(0, f_2) + \max(0, g_2) = 3$, and we have our answer.
The justification is that $\max(0,f_i) + \max(0, g_i)$ is the number of dresses that must pass through the $i-th$ washing machine, and this requires a minimum of $\max(0,f_i) + \max(0, g_i)$ moves because each dress requires 1 move. I understand this part, but apparently this lower bound is also the upper bound (and therefore the solution) and I don't understand why that is. Why can't the answer exceed $\max(0,f_i) + \max(0, g_i)$?