Placing Parentheses to Maximize Expression Value

Problem

Given a sequence of digits d1, d2, ..., dn and a sequence of binary operators op1, op2, ..., op(n-1) where each operator is in {'+', '-', '*'}, place parentheses to maximize the value of the arithmetic expression:

d1 op1 d2 op2 ... op(n-1) dn

Return the maximum achievable value.

This problem is similar in spirit to (but distinct from) LeetCode's "Different Ways to Add Parentheses" which asks for all possible results. Here we only need the maximum value.

Examples

Example 1

Input: expression = "1+2-3*4-5"
Output: 6
Explanation: One optimal parenthesization is ((1+2) - (3 * (4 - 5))) = (3 - (3 * (-1))) = 3 - (-3) = 6.

Example 2

Input: expression = "5-8+7*4-8+9"
Output: 200
Explanation: Maximum is achieved by 5 - ((8+7) * (4 - (8+9))) = 5 - (15 * (4 - 17)) = 5 - (15 * -13) = 5 - (-195) = 200.
Note: 32 (from 5 - 8 + (7 * (4 - 8 + 9))) is a valid achievable value but not the maximum.

Solution

Method 1 - Dynamic Programming (Min/Max Tables)

Intuition

• Parenthesization determines the order of operations. Splitting at an operator partitions the expression into a left sub-expression and a right sub-expression.
• Because subtraction and multiplication with negatives can flip sign, to compute the maximum for a range E(i, j) we need BOTH the minimum and maximum values of its left and right sub-ranges. Combining extremes (min/min, min/max, max/min, max/max) covers all possibilities.
• This mirrors matrix-chain or boolean parenthesization DP: store best (max) and worst (min) results for every interval and build up by increasing length.

Approach

1. Parse the input into two arrays:
   • nums = list of integers.
   • ops = list of operators between them.
2. Let n = len(nums). Create 2D arrays min_dp[n][n] and max_dp[n][n].
3. Initialize base cases: for every i, min_dp[i][i] = max_dp[i][i] = nums[i].
4. Iterate interval length L from 2 to n:
   • For each start i, set j = i + L - 1.
   • Initialize min_dp[i][j] = +inf, max_dp[i][j] = -inf.
   • For every split point k from i to j-1:
     • Operator at k is ops[k] (pairs nums[k] with nums[k+1]).
     • Enumerate four combinations:
       • (max_dp[i][k], max_dp[k+1][j])
       • (max_dp[i][k], min_dp[k+1][j])
       • (min_dp[i][k], max_dp[k+1][j])
       • (min_dp[i][k], min_dp[k+1][j])
     • Evaluate each with the operator and update interval min/max.
5. Result is max_dp[0][n-1].

Recurrence relation

Formal recurrence (Max / Min for an interval):

M(i,j) = maximum of sub-expression E(i,j); m(i,j) = minimum of E(i,j).

We denote by M(i,j) as the maximum value of the sub-expression spanning numbers ( i..j) (inclusive) and by m(i,j) its minimum. For any split position k with operator op_k between numbers k and k+1:

We compute subproblems in order of increasing length (j - i) ensuring dependencies ((i,k) and (k+1,j)) are ready:

Base case:

Edge cases

• Single number → the number itself.
• Expression with only additions → straightforward accumulation (still handled by DP).
• Negatives emerge via subtraction; multiplication of negatives can increase maximum.

Pseudocode

def min_and_max(i, j):
    min_val = +inf
    max_val = -inf
    for k in range(i, j):
        op = ops[k]
        a = M[i][k] op M[k+1][j]
        b = M[i][k] op m[k+1][j]
        c = m[i][k] op M[k+1][j]
        d = m[i][k] op m[k+1][j]
        min_val = min(min_val, a, b, c, d)
        max_val = max(max_val, a, b, c, d)
    return min_val, max_val

def maximize_expression(nums, ops):
    n = len(nums)
    for i in range(n):
        M[i][i] = nums[i]
        m[i][i] = nums[i]
    for L in range(2, n+1):
        for i in range(0, n-L+1):
            j = i + L - 1
            m[i][j], M[i][j] = min_and_max(i, j)
    return M[0][n-1]

Dry Run (Worked Example for 5-8+7*4-8+9)

Expression:

5 - 8 + 7 * 4 - 8 + 9

Parsed:

• Numbers (indices): 0:5, 1:8, 2:7, 3:4, 4:8, 5:9
• Operators (between i and i+1): 0:'-', 1:'+', 2:'*', 3:'-', 4:'+'

Base initialization:

m[i][i] = M[i][i] = [5, 8, 7, 4, 8, 9]

Upper-triangular DP tables ('.' = unused):

Minimum table m:

            j→    0      1      2      3      4       5
 i↓
 0         5     -3    -10    -55    -63     -94
 1         .      8     15     36    -60    -195
 2         .      .      7     28    -28     -91
 3         .      .      .      4     -4     -13
 4         .      .      .      .      8      17
 5         .      .      .      .      .       9

Maximum table M:

            j→    0      1      2      3      4      5
 i↓
 0         5     -3      4     25     65    200
 1         .      8     15     60     52     75
 2         .      .      7     28     20     35
 3         .      .      .      4     -4      5
 4         .      .      .      .      8     17
 5         .      .      .      .      .      9

Selected derivations:

• (0,1): 5 - 8 = -3 → m = M = -3.
• (1,3): 8 + 7 * 4:
  • Split k=1: 8 + (7*4) = 8 + 28 = 36
  • Split k=2: (8+7) * 4 = 15 * 4 = 60 → m=36, M=60.
• (2,4): 7 * 4 - 8:
  • k=2: 7 * (4 - 8) = 7 * -4 = -28
  • k=3: (7*4) - 8 = 28 - 8 = 20 → m=-28, M=20.
• (1,5) minimum -195 comes from (8+7) * (4 - (8+9)) = 15 * -13 = -195.
• Final max (0,5) = 200 via split k=0: 5 - ( (8+7) * (4 - (8+9)) ) = 200.

This confirms M[0][5] = 200.

Code

All implementations expose a function named maximizeExpression.

C++

#include <vector>
#include <string>
#include <cctype>
#include <limits>
#include <algorithm>
using namespace std;

class Solution {
    long apply(long a, long b, char op) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        return a * b; // '*'
    }
public:
    long maximizeExpression(const string &expr) {
        vector<long> nums; vector<char> ops;
        for (size_t i = 0; i < expr.size();) {
            if (isdigit(expr[i])) {
                long val = 0;
                while (i < expr.size() && isdigit(expr[i])) {
                    val = val * 10 + (expr[i]-'0');
                    ++i;
                }
                nums.push_back(val);
            } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
                ops.push_back(expr[i]);
                ++i;
            } else {
                ++i; // ignore spaces or others
            }
        }
        int n = (int)nums.size();
        if (n == 0) return 0;
        vector<vector<long>> mn(n, vector<long>(n, 0));
        vector<vector<long>> mx(n, vector<long>(n, 0));
        for (int i = 0; i < n; ++i) mn[i][i] = mx[i][i] = nums[i];
        for (int L = 2; L <= n; ++L) {
            for (int i = 0; i + L - 1 < n; ++i) {
                int j = i + L - 1;
                long curMin = numeric_limits<long>::max();
                long curMax = numeric_limits<long>::min();
                for (int k = i; k < j; ++k) {
                    char op = ops[k];
                    long a = apply(mx[i][k], mx[k+1][j], op);
                    long b = apply(mx[i][k], mn[k+1][j], op);
                    long c = apply(mn[i][k], mx[k+1][j], op);
                    long d = apply(mn[i][k], mn[k+1][j], op);
                    curMin = min({curMin, a, b, c, d});
                    curMax = max({curMax, a, b, c, d});
                }
                mn[i][j] = curMin; mx[i][j] = curMax;
            }
        }
        return mx[0][n-1];
    }
};

Go

package main

import (
    "unicode"
)

func maximizeExpression(expr string) int64 {
    var nums []int64
    var ops []rune
    for i := 0; i < len(expr); {
        if unicode.IsDigit(rune(expr[i])) {
            var val int64
            for i < len(expr) && unicode.IsDigit(rune(expr[i])) {
                val = val*10 + int64(expr[i]-'0')
                i++
            }
            nums = append(nums, val)
        } else if expr[i] == '+' || expr[i] == '-' || expr[i] == '*' {
            ops = append(ops, rune(expr[i]))
            i++
        } else { i++ }
    }
    n := len(nums)
    if n == 0 { return 0 }
    mn := make([][]int64, n)
    mx := make([][]int64, n)
    for i := range mn { mn[i] = make([]int64, n); mx[i] = make([]int64, n) }
    for i := 0; i < n; i++ { mn[i][i] = nums[i]; mx[i][i] = nums[i] }
    apply := func(a, b int64, op rune) int64 {
        switch op { case '+': return a + b; case '-': return a - b; default: return a * b }
    }
    for L := 2; L <= n; L++ {
        for i := 0; i+L-1 < n; i++ {
            j := i + L - 1
            curMin := int64(1<<63 - 1)
            curMax := int64(-1 << 63)
            for k := i; k < j; k++ {
                op := ops[k]
                a := apply(mx[i][k], mx[k+1][j], op)
                b := apply(mx[i][k], mn[k+1][j], op)
                c := apply(mn[i][k], mx[k+1][j], op)
                d := apply(mn[i][k], mn[k+1][j], op)
                if a < curMin { curMin = a }; if a > curMax { curMax = a }
                if b < curMin { curMin = b }; if b > curMax { curMax = b }
                if c < curMin { curMin = c }; if c > curMax { curMax = c }
                if d < curMin { curMin = d }; if d > curMax { curMax = d }
            }
            mn[i][j] = curMin; mx[i][j] = curMax
        }
    }
    return mx[0][n-1]
}

Java

import java.util.*;

class Solution {
    public long maximizeExpression(String expr) {
        List<Long> nums = new ArrayList<>();
        List<Character> ops = new ArrayList<>();
        for (int i = 0; i < expr.length();) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                long val = 0;
                while (i < expr.length() && Character.isDigit(expr.charAt(i))) {
                    val = val * 10 + (expr.charAt(i) - '0');
                    i++;
                }
                nums.add(val);
            } else if (c == '+' || c == '-' || c == '*') {
                ops.add(c); i++;
            } else {
                i++; // skip spaces
            }
        }
        int n = nums.size();
        if (n == 0) return 0L;
        long[][] mn = new long[n][n];
        long[][] mx = new long[n][n];
        for (int i = 0; i < n; i++) mn[i][i] = mx[i][i] = nums.get(i);
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i + L - 1 < n; i++) {
                int j = i + L - 1;
                long curMin = Long.MAX_VALUE;
                long curMax = Long.MIN_VALUE;
                for (int k = i; k < j; k++) {
                    char op = ops.get(k);
                    long a = apply(mx[i][k], mx[k+1][j], op);
                    long b = apply(mx[i][k], mn[k+1][j], op);
                    long c = apply(mn[i][k], mx[k+1][j], op);
                    long d = apply(mn[i][k], mn[k+1][j], op);
                    curMin = Math.min(Math.min(Math.min(curMin, a), Math.min(b, c)), d);
                    curMax = Math.max(Math.max(Math.max(curMax, a), Math.max(b, c)), d);
                }
                mn[i][j] = curMin; mx[i][j] = curMax;
            }
        }
        return mx[0][n-1];
    }

    private long apply(long a, long b, char op) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        return a * b;
    }
}

Python

from typing import List, Tuple

class Solution:
    def maximizeExpression(self, expr: str) -> int:
        nums: List[int] = []
        ops: List[str] = []
        i = 0
        while i < len(expr):
            c = expr[i]
            if c.isdigit():
                val = 0
                while i < len(expr) and expr[i].isdigit():
                    val = val * 10 + int(expr[i])
                    i += 1
                nums.append(val)
            elif c in '+-*':
                ops.append(c)
                i += 1
            else:
                i += 1  # skip spaces / others
        n = len(nums)
        if n == 0:
            return 0
        min_dp = [[0]*n for _ in range(n)]
        max_dp = [[0]*n for _ in range(n)]
        for i in range(n):
            min_dp[i][i] = max_dp[i][i] = nums[i]
        def apply(a: int, b: int, op: str) -> int:
            if op == '+':
                return a + b
            if op == '-':
                return a - b
            return a * b
        for L in range(2, n+1):
            for i in range(0, n-L+1):
                j = i + L - 1
                cur_min = 10**18
                cur_max = -10**18
                for k in range(i, j):
                    op = ops[k]
                    a = apply(max_dp[i][k], max_dp[k+1][j], op)
                    b = apply(max_dp[i][k], min_dp[k+1][j], op)
                    c = apply(min_dp[i][k], max_dp[k+1][j], op)
                    d = apply(min_dp[i][k], min_dp[k+1][j], op)
                    cur_min = min(cur_min, a, b, c, d)
                    cur_max = max(cur_max, a, b, c, d)
                min_dp[i][j] = cur_min
                max_dp[i][j] = cur_max
        return max_dp[0][n-1]

Complexity

• ⏰ Time complexity: O(n^3) — there are O(n^2) intervals and each considers O(n) split points; constant work per split (4 combinations).
• 🧺 Space complexity: O(n^2) for the two DP tables min_dp and max_dp.