"Maximizing Your Salary"

In this homework assignment, you'll design and implement an algorithm to create the largest number out of arbitrary positive integers Problem Introduction As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this? In the lectures, we discussed an algorithm for composing the largest number out of the given single-digit numbers For example, what is the largest number that consists of digits 3, 9,5, 9,7, 1 using all the digits? The answer was 997531 using the following greedy approach. LargestNumber (Digits answer empty string while Digits is not empty maxDigit -00 for digit in Digits: if digit maxDigit maxDigit digit append maxDigit to answer remove maxDigit from Digits return answer Unfortunately, this algorithm works only in case the input consists of single-digit numbers. For example, fo an input consisting of two integers 23 and 3 (23 is not a single-digit number!) it returns 233, while the largest number is in fact 323. In other words, using the largest number from the input as the first number is not a safe move. Thus, your goal in this problem is to tweak the above algorithm so that it works not only for single-digit numbers but for arbitrary positive integers Problem Description Task: Compose the largest number o of set of integers. Input Format: The first line of the input contains an integer n. The second line contains integers a a2, ...,an o You can create your own input file for testing. I will test with a different input file. Constraints: 1 sn s 100; 1 s ais 103 for all 1 sis n. output Format: output the largest number that can be composed out of a1, a2, ...,an Time Limit 0.01 second for Clanguage, 0.02 second for Java, when n 100