Proof for This Greedy Strategy for Equalizing An Array
Actually I am not sure the greedy solution will always give the best solution?

Recall that the change making problem does not work for certain denominations in a greedy way. For example with denominations $1,3,4$ and a goal of $6$ the greedy solution will give $4,1,1$ whereas the optimal solution is $3,3$.

This can be translated into your problem. Start with array $A=[0,6]$ and steps $D=\{1,3,4\}$. Now your greedy solution seems to behave like change making. I am not certain about this, however, as your description does not precisely say by which amount the numbers are incremented. Perhaps your algorithm chooses $[0,6] \to [4,6] \to [7,6] \to [7,7]$ (which is also wrong, anyway).