Solution: Maximum Salary

Solutions for the Largest Concatenate Problem.

We'll cover the following

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.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.