If you apply the greedy algorithm, that is very close to asking for the maximum drawdown of a random walk with positive drift.
The distribution of maximum drawdowns of a Brownian motion with constant drift have been studied, and some answers are on page 2 here. The expected maximum drawdown with positive drift grows asymptotically like $c \log M$. I'm not sure how the tails look.
I asked how badly the Brownian approximation behaves for discrete walks here. It can be far off for some skewed distributions, but it should be off by a small constant factor for these nearly symmetric steps.
The globally optimal adjustments can't reduce the maximum excursion by more than a factor of 2 compared with the greedy algorithm, since on the largest (without loss of generality) positive excursion to $d$, the greedy algorithm was all -1s. Then any change made would still mean the walk increases by at least $d$, so at best a global optimization could move the start to $-d/2$ which would make the maximum at least $d/2$ in both directions.
