Our task is to rearrange the string of digits into two integers a and b such that a + b is as large as possible. Let’s see how we can construct such a and b, and thus find the value of a + b.
In the easy subproblem, we had exactly three digits. The answer will certainly be of the form $\overline{ab}+\overline{\vphantom{b}c}$, where a, b and c are the three given digits (in some order), and the overline denotes a number that consists of the given digits.
The value of the above number is 10a + b + c. From this it is obvious that a should be the largest of the three given digits and that the order of b and c does not matter.
The above observation can easily be generalized to solve the hard subproblem as well. The optimal solution is to read the string of digits, sort them in non-ascending order, and then take the first n − 1 digits as one of the numbers and the last digit as the other number. For example, the optimal solution for the input 12345 is 5432+1.
It is easy to verify that the solution described above will never run into troubles with unnecessary leading zeros – if there are zeros in the input, one of them will be b (which is valid) and all others will be at the end of a (which is also valid).
Lemma: In the optimal solution one of the two numbers will consist of just a single digit.
Proof: Consider an arbitrary arrangement of digits. Label the two numbers a and b so that a > b. Suppose that b has more than one digit. Let’s now take the last digit of b and append it to a instead. It should be obvious that we didn’t create any new leading zeros anywhere, so the solution remains valid.
How will the sum change? Let’s write the original b as 10b′ + d. The sum before we moved the digit was a + 10b′ + d. After the move the new sum is 10a + d + b′. The change is 9(a − b′) > 0, therefore the new arrangement is better than the old one, so the old arrangement cannot be optimal.
Theorem: The arrangement described in our solution above is optimal.
Proof: From the lemma we know that each optimal solution has the form $\overline{d_1\dots d_{n-1}} + \overline{d_n}$. The value of this number is 10n − 2d1 + 10n − 3d2 + ⋯ + 10dn − 2 + dn − 1 + dn.
Hence, it is clearly optimal to assign the largest digit to d1, the second largest to d2, and so on. The order of the last two digits does not matter.