Optimal Division

Problem Statement

Given an integer array nums, each element is divided by its subsequent neighbor forming a float division chain expression of the format "nums[0]/nums[1]/.../nums[n-1]". You can manipulate this expression by strategically placing parentheses to affect the computation order and maximize the final result. The goal is to determine where these parentheses should be placed to achieve the maximum possible division result, and then return the maximized expression in string format without any redundant parentheses.

Examples

Example 1

Input:

nums = [1000,100,10,2]

Output:

"1000/(100/10/2)"

Explanation:

1000/(100/10/2) = 1000/((100/10)/2) = 200

However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Example 2

Input:

nums = [2,3,4]

Output:

"2/(3/4)"

Explanation:

(2/(3/4)) = 8/3 = 2.667

It can be shown that after trying all possibilities, we cannot get an expression with evaluation greater than 2.667

Constraints

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• There is only one optimal division for the given input.

Approach and Intuition

To solve this problem, we need to understand how division operations are affected by the order of execution, particularly when parentheses alter this order.

1. Priority of Division: In floating-point divisions, dividing by a smaller number increases the quotient, hence to maximize the result, we sometimes need to ensure that divisions happen in a manner where smaller results are not prematurely further divided.

2. Strategic Parentheses Placement:

   • When the array has more than two numbers, the maximum result can generally be achieved by dividing the first number by the result of the subsequent chain of divisions. This is because dividing by a bigger number results from the chain would decrease the overall value.
   • Expressions like A/(B/C/D) ensure that B, C, and D are first evaluated to a smaller number which when divided into A yields a larger value.

3. Constructing the Expression:

   • If the input list only contains one or two numbers, the maximum result is simply the straightforward division of these numbers.
   • For more than two numbers, to maximize the division, you would ideally want to divide the first number by the division of all subsequent numbers. Therefore, the general form would be:
     • For nums = [a, b, c, d], the optimal division string would be "a/(b/c/d)". This setup reduces the impact of the division chain on reducing a by first reducing the impact of all b, c, d on each other.

4. Generating the Optimal Expression:

   • If nums length is 1, simply return the number.
   • If nums length is 2, return the expression "nums[0]/nums[1]".
   • For lengths greater than 2: Build the string such that the first number is divided by the enclosed expression of the remaining numbers. This is done by joining all numbers from the second to the last with "/" and wrapping them in a single parenthesis, prefixed by the division operation with the first number.

With this approach, we ensure that the parentheses we add are purposeful and not redundant, strictly influencing the computation order to maximize the result.

Solutions

public class Solution {
    public String divisionMaximization(int[] array) {
        if (array.length == 1)
            return String.valueOf(array[0]);
        if (array.length == 2)
            return array[0] + "/" + array[1];
        StringBuilder result = new StringBuilder(array[0] + "/(" + array[1]);
        for (int index = 2; index < array.length; index++) {
            result.append("/" + array[index]);
        }
        result.append(")");
        return result.toString();
    }
}