Solution: Maximum Salary

Solution

Recall the algorithm for this problem that works for single-digit numbers.

---

 $LargestConcatenate(Numbers)$:
 $yourSalary$ $\leftarrow$ empty string
 while $Numbers$ is not empty:
  $maxNumber$ $\leftarrow$ -$\infty$
  for each $Number$ in $Numbers$:
   if $number$ $\geq$ $maxNumber$:
    $maxNumber$ $\leftarrow$ $number$
  append $maxNumber$ from $yourSalary$
  remove $maxNumber$ from $Numbers$
return $yourSalary$

---

As we already know, this algorithm does not always maximize your salary. For example, for an input consisting of two integers, $23$ and $3$, it returns $233$, while the largest number is $323$.

Not to worry, all you need to do to maximize your salary is replace the line

---

 if $number$ ≥ $maxNumber$:

---

with the following line

---

 if $IsBetter(number,maxNumber)$:

---

for an appropriately implemented function IsBetter. For example, IsBetter(3, 23) should return True.

Stop and think: How would you implement IsBetter?

Code

Here is the code for the algorithm discussed above. Click the “Run” button to see how it works.