Min and Max of Arithmetic Expression with + and * (Interval DP)

Given an arithmetic expression of numbers joined by + and *, placing parentheses in different positions can produce very different results: for 1+2*3+4*5, the achievable range is 27 (minimum) to 105 (maximum).

This is a classic interval dynamic programming problem that appears in technical placement rounds for product and analytics roles. The goal is not to evaluate a fixed expression, but to find both the smallest and largest values obtainable by any valid parenthesisation.

What the Problem Is Asking

The standard BODMAS rule gives * higher precedence than +, so 1+2*3+4*5 evaluates to 27 under normal arithmetic. But this problem asks: if you can place parentheses freely, what is the full range of results?

Two concrete parenthesisations for the same input illustrate the extremes:

• Minimum (27): 1 + (2 * 3) + (4 * 5) = 1 + 6 + 20 = 27
• Maximum (105): (1 + 2) * (3 + 4) * 5 = 3 * 7 * 5 = 105

The numbers are the same. The operators are the same. Only the grouping changes.

Input format: a string like "1+2*3+4*5" containing positive integers separated by + or *. No spaces, no subtraction, no division.

Why Brute Force Does Not Scale

For an expression with n operands, the number of distinct parenthesisations equals the (n-1)th Catalan number. For our 5-operand example, that is the 4th Catalan number = 14. That sounds manageable. But Catalan numbers grow exponentially: 14 parenthesisations for 5 operands becomes 132 for 7 operands, 4,862 for 10 operands, and over 35,000 for 12 operands.

Generating and evaluating every parenthesisation by brute force is O(n * Catalan(n)), which effectively means exponential time. Dynamic programming brings this down to a polynomial O(n³) by recognising that sub-expression results are reused across parenthesisations.

A similar DP approach over integer ranges avoids re-computing overlapping sub-problems in related number-theory questions.

The Interval DP Approach

Interval DP (also called range DP) is structurally identical to Matrix Chain Multiplication, where you optimise the order of combining matrices. Here, you optimise the order of combining operands.

State:

• dp_min[i][j] = the minimum value achievable for the sub-expression covering operands i through j.
• dp_max[i][j] = the maximum value achievable for the same range.

Base case: A single operand has exactly one value: dp_min[i][i] = dp_max[i][i] = nums[i].

Transition: For every sub-expression [i, j], try every split point k from i to j-1. The operator at position k (i.e., ops[k]) sits between operand k and operand k+1:

• If ops[k] == '+':
  • val_min = dp_min[i][k] + dp_min[k+1][j] (sum of minimums is the smallest sum)
  • val_max = dp_max[i][k] + dp_max[k+1][j] (sum of maximums is the largest sum)
• If ops[k] == '*':
  • Compute all four products: lmin * rmin, lmin * rmax, lmax * rmin, lmax * rmax
  • val_min = min of the four; val_max = max of the four
  • (The four-product rule is needed for correctness when negatives are present, and it costs nothing to include it.)

Update dp_min[i][j] and dp_max[i][j] by comparing across all k.

The space complexity of this algorithm is O(n²) for the two n × n tables, and the time complexity is O(n³).

Worked Example: 1+2*3+4*5

Numbers: [1, 2, 3, 4, 5]. Operators: [+, *, +, *] (operator at index k sits between nums[k] and nums[k+1]).

Length-1 (base cases):

• dp[0][0] = 1, dp[1][1] = 2, dp[2][2] = 3, dp[3][3] = 4, dp[4][4] = 5

Length-2:

• dp[0][1]: ops[0]=+, only split at k=0: 1+2=3. Min=Max=3.
• dp[1][2]: ops[1]=*, 2*3=6. Min=Max=6.
• dp[2][3]: ops[2]=+, 3+4=7. Min=Max=7.
• dp[3][4]: ops[3]=*, 4*5=20. Min=Max=20.

Length-3:

• dp[0][2]: split at k=0 (op +): 1+6=7; split at k=1 (op *): 3*3=9. Min=7, Max=9.
• dp[1][3]: split at k=1 (op *): 2*7=14; split at k=2 (op +): 6+4=10. Min=10, Max=14.
• dp[2][4]: split at k=2 (op +): 3+20=23; split at k=3 (op *): 7*5=35. Min=23, Max=35.

Length-4:

• dp[0][3]: k=0 (op +): min 1+10=11, max 1+14=15; k=1 (op *): 3*7=21; k=2 (op +): min 7+4=11, max 9+4=13. Min=11, Max=21.
• dp[1][4]: k=1 (op *): min 223=46, max 235=70; k=2 (op +): 6+20=26; k=3 (op *): min 105=50, max 145=70. Min=26, Max=70.

Length-5 (full expression):

• k=0 (op +): min 1+26=27, max 1+70=71.
• k=1 (op *): min 323=69, max 335=105.
• k=2 (op +): min 7+20=27, max 9+20=29.
• k=3 (op *): min 115=55, max 215=105.
• dp_min[0][4] = min(27, 69, 27, 55) = 27 ✓
• dp_max[0][4] = max(71, 105, 29, 105) = 105 ✓

Both match the expected output.

Python Implementation

def min_max_expression(expr: str) -> tuple[int, int]:
    # --- Parse expression into nums and ops lists ---
    nums, ops = [], []
    i = 0
    while i < len(expr):
        num = 0
        while i < len(expr) and expr[i].isdigit():
            num = num * 10 + int(expr[i])
            i += 1
        nums.append(num)
        if i < len(expr):
            ops.append(expr[i])   # '+' or '*'
            i += 1

    n = len(nums)
    INF = float('inf')
    dp_min = [[INF]  * n for _ in range(n)]
    dp_max = [[-INF] * n for _ in range(n)]

    # Base case: single operand
    for i in range(n):
        dp_min[i][i] = dp_max[i][i] = nums[i]

    # Fill by increasing sub-expression length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1          # right endpoint of sub-expression
            for k in range(i, j):       # split point: ops[k] is between k and k+1
                lmin, lmax = dp_min[i][k], dp_max[i][k]
                rmin, rmax = dp_min[k + 1][j], dp_max[k + 1][j]

                if ops[k] == '+':
                    val_min = lmin + rmin
                    val_max = lmax + rmax
                else:  # '*'
                    products = [lmin * rmin, lmin * rmax,
                                lmax * rmin, lmax * rmax]
                    val_min, val_max = min(products), max(products)

                dp_min[i][j] = min(dp_min[i][j], val_min)
                dp_max[i][j] = max(dp_max[i][j], val_max)

    return dp_min[0][n - 1], dp_max[0][n - 1]


# Example
minimum, maximum = min_max_expression("1+2*3+4*5")
print(minimum, maximum)   # 27 105

Complexity summary:

• Time: O(n³) — three nested loops over sub-expression bounds and split points.
• Space: O(n²) — two n × n DP tables plus O(n) for the parsed lists.

The approach extends naturally to expressions with symmetric or pairwise structure in arrays where overlapping sub-problem optimisation applies.

---

Interval DP teaches one durable insight: the order in which you combine sub-results determines the final value. That same principle appears in multi-step LLM prompt pipelines, where chaining prompts in different orders produces measurably different accuracy. If you want a live environment to run those chain-optimisation experiments without setting up infrastructure, TinkerLLM offers a hands-on playground at ₹299.