I saw this task in a programming competition, and I solved it, however, I just guessed the answer and don't know how to prove that it works.
As it turns out, to get the maximum, you have to make the number $a$ such that its digits 2nd through last are all nines, and the first digit of $a$ is (the first digit of $n$) - 1. (Parenthesis mean that we subtract 1 from the first digit, and not from $n$ itself).
$n$ is 2542, in that case $a$ is 1999.
Why does this work?