Problem Brief
Maximum Sum After Merges
OA
See Microsoft online assessment and hiring insights
There is an array A of N non-negative integers. Any two initial elements of A that are adjacent can be replaced with their merged equivalent. For example, given A = [2, 3, 15], pair (2, 3) can be replaced with 23, resulting in array [23, 15], and pair (3, 15) can be replaced with 315, resulting in array [2, 315]. The result of the merge cannot be merged any further, so we can't get 2315 in the example above. What is the maximum possible sum of elements of A after any number of merges?
Write a function that, given an array A of N non-negative integers, returns the maximum sum of elements of A after any number of merges.
1Example 1
Input
A = [2, 2, 3, 5, 4, 0]
Output
97
Explanation
We can merge elements of the following pairs: (2, 2), (3, 5) and (4, 0). This results in A = [22, 35, 40], which sums up to 97.
2Example 2
Input
A = [3, 19, 191, 91, 3]
Output
20107
Explanation
We can merge elements of the following pairs: (19, 191) and (91, 3). This results in A = [3, 19191, 913], which sums up to 20107.
3Example 3
Input
A = [12, 6, 18, 10, 1, 0]
Output
1946
Explanation
The merges should make A = [126, 1810, 10], which sums up to 1946.
4Example 4
Input
A = [2, 1, 0, 1, 2, 9, 1, 0]
Output
124
Explanation
The merges should make A = [21, 0, 12, 91, 0], which sums up to 124.
Constraints
Limits and guarantees your solution can rely on.
N is an integer within the range [1..10,000]Each element of array A is an integer within the range [0..200]