# Optimal Division
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/optimal-division)
Canonical: https://scaleengineer.com/dsa/problems/optimal-division
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`. The adjacent integers in `nums` will perform the float division.

* For example, for `nums = [2,3,4]`, we will evaluate the expression `"2/3/4"`.

However, you can add any number of parenthesis at any position to change the priority of operations. You want to add these parentheses such the value of the expression after the evaluation is maximum.

Return _the corresponding expression that has the maximum value in string format_.

**Note:** your expression should not contain redundant parenthesis.

**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.

# Approaches
## Dynamic Programming with Memoization
This approach exhaustively explores all possible ways to place parentheses to find the optimal solution. We can define a recursive function that computes the maximum and minimum possible values for any sub-array `nums[i...j]`. To avoid the exponential complexity of pure recursion, we use memoization (a top-down dynamic programming technique) to store and reuse the results for subproblems.
**Time:** O(N^3). There are `O(N^2)` possible subproblems (states `(i, j)`). To compute each state, we iterate through `O(N)` possible split points `k`. The recursive calls are `O(1)` due to memoization. Thus, the total time complexity is `O(N^2 * N) = O(N^3)`. · **Space:** O(N^3). The memoization tables `memoMax` and `memoMin` require `O(N^2)` space. However, each entry in the table stores a string expression, which can have a length of up to `O(N)`. This leads to a total space complexity of `O(N^2 * N) = O(N^3)`.
**Pros:** Guaranteed to find the correct optimal solution by exploring all valid parenthesizations.; It's a general method that can be adapted for similar problems with different operators or constraints.
**Cons:** The time and space complexity are high (`O(N^3)`), making it inefficient for larger constraints.; The implementation is more complex compared to the simpler greedy approach.
### Explanation
We define two mutually recursive functions, `getMax(i, j)` and `getMin(i, j)`, which compute the maximum and minimum value obtainable from the sub-array `nums[i...j]`, respectively. They also return the string expression that yields this value. The state for our recursion is `(i, j)`, and we use two 2D arrays, `memoMax` and `memoMin`, to store the computed results.

**Base Case:** If `i == j`, the sub-array has one element. The max and min values are both `nums[i]`, and the expression is just the number itself as a string.

**Recursive Step:** To compute `getMax(i, j)`, we iterate through all possible split points `k` from `i` to `j-1`. A split at `k` divides the expression into `(nums[i]...nums[k]) / (nums[k+1]...nums[j])`. To maximize this division, we must maximize the numerator and minimize the denominator. So, we recursively call `getMax(i, k)` and `getMin(k+1, j)`. We do this for all `k` and take the overall maximum. Similarly, to compute `getMin(i, j)`, we need to minimize the numerator and maximize the denominator, so we call `getMin(i, k)` and `getMax(k+1, j)`.

When constructing the expression string from `expr1` and `expr2`, we add parentheses around `expr2` if it corresponds to a sub-array of length greater than 1 to maintain the correct order of operations. The final answer is the string returned by `getMax(0, n-1)`.

```java
class Solution {
    class Result {
        double value;
        String str;
        Result(double v, String s) {
            this.value = v;
            this.str = s;
        }
    }

    private Result[][] memoMax;
    private Result[][] memoMin;
    private int[] nums;

    public String optimalDivision(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memoMax = new Result[n][n];
        memoMin = new Result[n][n];
        return findMax(0, n - 1).str;
    }

    private Result findMax(int i, int j) {
        if (memoMax[i][j] != null) {
            return memoMax[i][j];
        }
        if (i == j) {
            return new Result(nums[i], String.valueOf(nums[i]));
        }

        Result maxRes = new Result(-1.0, "");

        for (int k = i; k < j; k++) {
            Result left = findMax(i, k);
            Result right = findMin(k + 1, j);
            double val = left.value / right.value;
            if (val > maxRes.value) {
                maxRes.value = val;
                String rightStr = right.str;
                if (k + 1 < j) { // Denominator is a complex expression
                    rightStr = "(" + rightStr + ")";
                }
                maxRes.str = left.str + "/" + rightStr;
            }
        }
        return memoMax[i][j] = maxRes;
    }

    private Result findMin(int i, int j) {
        if (memoMin[i][j] != null) {
            return memoMin[i][j];
        }
        if (i == j) {
            return new Result(nums[i], String.valueOf(nums[i]));
        }

        Result minRes = new Result(Double.MAX_VALUE, "");

        for (int k = i; k < j; k++) {
            Result left = findMin(i, k);
            Result right = findMax(k + 1, j);
            double val = left.value / right.value;
            if (val < minRes.value) {
                minRes.value = val;
                String rightStr = right.str;
                if (k + 1 < j) { // Denominator is a complex expression
                    rightStr = "(" + rightStr + ")";
                }
                minRes.str = left.str + "/" + rightStr;
            }
        }
        return memoMin[i][j] = minRes;
    }
}
```
### Algorithm
1. Define a recursive function, say `solve(i, j)`, that computes the maximum and minimum possible values for the sub-array `nums[i...j]`.
2. The state for our recursion/DP is the pair of indices `(i, j)`.
3. Use two 2D arrays, `memoMax[n][n]` and `memoMin[n][n]`, to store the computed results (memoization) to avoid redundant calculations. Each entry will store both the computed value and the corresponding string expression.
4. **Base Case:** If `i == j`, the sub-array has only one element. The maximum and minimum values are both `nums[i]`, and the expression is simply `String.valueOf(nums[i])`.
5. **Recursive Step:** To compute the result for `(i, j)`, we iterate through all possible split points `k` from `i` to `j-1`. A split at `k` corresponds to the expression `(nums[i]...nums[k]) / (nums[k+1]...nums[j])`.
   - To find the maximum value for `(i, j)`, we need to maximize the numerator and minimize the denominator. So, for each `k`, we calculate `solve(i, k).maxValue / solve(k+1, j).minValue`.
   - To find the minimum value for `(i, j)`, we need to minimize the numerator and maximize the denominator. So, for each `k`, we calculate `solve(i, k).minValue / solve(k+1, j).maxValue`.
6. We keep track of the split `k` that yields the best result and construct the expression string accordingly.
7. **String Construction:** When combining two sub-expressions `expr1` and `expr2` as `expr1 / expr2`, if `expr2` corresponds to a sub-array of length greater than 1 (i.e., it already contains a division), it must be enclosed in parentheses to ensure correct precedence. For example, `A / (B/C)`.
8. The final answer is the string part of the result of `solve(0, n-1).maxValue`.

## Mathematical Greedy Approach
A closer analysis of the expression `x1 / x2 / ... / xn` reveals a simple greedy strategy. To maximize a fraction, we aim to maximize the numerator and minimize the denominator. The structure of the division chain allows for a straightforward way to achieve this, leading to a highly efficient solution.
**Time:** O(N). We iterate through the input array once to build the result string. · **Space:** O(N). We use a `StringBuilder` to construct the result string. The length of the final string is proportional to the number of elements and their digits, which is `O(N)`.
**Pros:** Extremely efficient, with linear time and space complexity.; The implementation is very simple and concise.; It directly constructs the single optimal solution without exploring other possibilities.
**Cons:** The logic is based on a specific mathematical property of division and positive numbers, so it's not a general-purpose algorithm for expression evaluation problems.
### Explanation
The expression we want to maximize is `x1 / x2 / x3 / ... / xn`. We can group this as `x1 / D`, where `D` is the result of evaluating `x2 / x3 / ... / xn` with some parentheses. To maximize the total value, we must minimize the value of the denominator `D` (since `x1` is fixed and all numbers are positive).

Let's analyze `D = x2 / x3 / ... / xn`. Since all numbers are `> 1`, to minimize this expression, we want to divide `x2` by the largest possible number we can form from `x3, ..., xn`. The largest possible denominator is formed by multiplying all subsequent numbers together: `x3 * x4 * ... * xn`.

Conveniently, the standard left-to-right evaluation of `x2 / x3 / ... / xn` (i.e., `((x2 / x3) / x4) ...`) results in `x2 / (x3 * x4 * ... * xn)`. This gives the smallest possible value for `D`.

Therefore, the optimal strategy is to group the entire sub-expression from the second number onwards. The resulting expression is `x1 / (x2 / x3 / ... / xn)`. This maximizes the overall value.

For small arrays (`n <= 2`), no parentheses are needed. For `n > 2`, we apply the pattern `x1/(x2/.../xn)`.

```java
public class Solution {
    public String optimalDivision(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return String.valueOf(nums[0]);
        }
        if (n == 2) {
            return nums[0] + "/" + nums[1];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(nums[0]).append("/(");
        for (int i = 1; i < n; i++) {
            sb.append(nums[i]);
            if (i < n - 1) {
                sb.append("/");
            }
        }
        sb.append(")");

        return sb.toString();
    }
}
```
### Algorithm
1. Handle the edge cases first. If the array has 1 or 2 elements, no parentheses are needed.
   - If `n == 1`, return `nums[0]`.
   - If `n == 2`, return `nums[0] + "/" + nums[1]`.
2. If the array has more than 2 elements (`n > 2`), apply the greedy strategy.
3. Construct the result string by taking the first element `nums[0]`, followed by `"/("`. 
4. Iterate from the second element `nums[1]` to the last element `nums[n-1]`, appending them to the string, separated by `/`.
5. Finally, append the closing parenthesis `")"`.
6. Return the constructed string.

# Solutions
### Java

```java
class Solution {
public
  String optimalDivision(int[] nums) {
    int n = nums.length;
    if (n == 1) {
      return nums[0] + "";
    }
    if (n == 2) {
      return nums[0] + "/" + nums[1];
    }
    StringBuilder ans = new StringBuilder(nums[0] + "/(");
    for (int i = 1; i < n - 1; ++i) {
      ans.append(nums[i] + "/");
    }
    ans.append(nums[n - 1] + ")");
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string optimalDivision(vector<int> &nums) {
    int n = nums.size();
    if (n == 1)
      return to_string(nums[0]);
    if (n == 2)
      return to_string(nums[0]) + "/" + to_string(nums[1]);
    string ans = to_string(nums[0]) + "/(";
    for (int i = 1; i < n - 1; i++)
      ans.append(to_string(nums[i]) + "/");
    ans.append(to_string(nums[n - 1]) + ")");
    return ans;
  }
};

```

### Python

```python
class Solution:
    def optimalDivision(self, nums: List[int]) -> str: n = len(nums) if n == 1: return str(nums[0]) if n == 2: return f ' { nums [ 0 ] } / { nums [ 1 ] } ' return f ' { nums [ 0 ] } /( { "/" . join ( map ( str , nums [ 1 : ])) } )'

```