How to come up with a greedy solution and prove it?
Show the following two statements (I guess they would be lemmas):
When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$
For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.
Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.