Maximum Sum After Merges

Problem Overview

• Given an array of N non-negative integers, replace any adjacent pair of initial elements with their digit-concatenation to maximize the final array sum.
• Input: A with N in [1..10,000], values in [0..200]; Output: the maximum possible sum; merged results cannot be merged again.
• Context: Optimization in arrays and number manipulation using concatenation.
• This is a Microsoft coding interview problem and a common interview question.