# maximum expression by adding parentheses
## problem:
Describe and analyze an algorithm to compute, given a list of integers separated by + and − signs, the maximum possible value the expression can take by adding parentheses. Parentheses must be used only to group additions and subtractions; in particular, do not use them to create implicit multiplication.
## algorithm:
Similar to matrix chain multiplication, we can utilize interval dynamic programming. Define nums[i] as the ith number and ops[i] as the operator (either + or -) between nums[i] and nums[i + 1]. Then define two DP tables, maxVal[i][j] as the maximum value we can get the subexpression nums[i] to nums[j] and minVal[i][j] as the minimum value from the subexpression. Two tables are necessary as the subtraction operator can turn a large negative into a large positive and must be considered.

The base case when there is only a single element in the subexpression is maxVal[i][i] = minVal[i][i] = nums[i]. For every possible split point k between i and j for each larger range [i...j], subexpression = (nums[i] ... nums[k]) op[k] (nums[k + 1] ... nums[k]). Then, combine according to op[k]. If op[k] == '+', maxVal[i][j] = max(maxVal[i][j], maxVal[i][k] + maxVal[k+1][j]) and minVal[i][j] = min(minVal[i][j], minVal[i][k] + minVal[k+1][j]), else if op[k] == '-' maxVal[i][j] = max(maxVal[i][j], maxVal[i][k] - minVal[k+1][j]) and minVal[i][j] = min(minVal[i][j], minVal[i][k] - maxVal[k+1][j]).
""

// input: array of numbers and array of operators between those numbers
// output: the maximum value of the expression through addition of parentheses
int maxExpressionValue(vector<int> nums, vector<char> ops) {
    int n = nums.size();
    
    // create 2d arrays
    vector<vector<int>> maxVal(n, vector<int>(n));
    vector<vector<int>> minVal(n, vector<int>(n));
    
    // base cases
    for (int i = 0; i < n; i++) {
        maxVal[i][i] = minVal[i][i] = nums[i];
    }
    
    // length of subexpression
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;
            // initalize maximum and minimums
            maxVal[i][j] = (int minimum);
            minVal[i][j] = (int maximum);
            
            for (int k = i; k < j; k++) {
                if (ops[k] == '+') {
                    maxVal[i][j] = max(maxVal[i][j], maxVal[i][k] + maxVal[k+1][j]);
                    minVal[i][j] = min(minVal[i][j], minVal[i][k] + minVal[k+1][j]);
                }
                // else ops[k] == '-'
                else {
                    maxVal[i][j] = max(maxVal[i][j], maxVal[i][k] - minVal[k+1][j]);
                    minVal[i][j] = min(minVal[i][j], minVal[i][k] - maxVal[k+1][j]);
                }
            }
        }
    }
    return maxVal[0][n-1];
}

// sample call
// standard input: 1 + 3 - 2 - 5 + 1 - 6 + 7
// separate into two arrays (not relevant to scope of problem):
// vector<int> nums = {1, 3, 2, 5, 1, 6, 7}
// vector<char> ops = {+, -, -, +, -, +}
// int maxExpressionValue(nums, ops)    // expect 9

## correctness:
#### Theorem:
The algorithm correctly identifies both the true maximum and minimum value after parenthesization for any input.
#### Proof:
Proof by induction on length l = j - i + 1.
Base case (l = 1): When i = j, the subexpression is a single number, meaning that the only parenthesization trivially yields the value nums[i]. The algorithm accounts for this in this line by setting maxVal[i][i] = minVal[i][i] = nums[i], which means it correctly identifies the true maximum and minimum values.

Inductive hypothesis: Assume for all intervals of length < l, the algorithm correctly computes maxVal and minVal.

Inductive step (prove for all intervals of length ≥ 2): Fix an interval [i, j] with j - i + 1 = l. Consider any full parenthesization of the subexpression. Any such one has a top-level binary split: there exists some k with i ≤ k < j s.t. the topmost operation combines a left subexpression over [i...k] and a right one over [k + 1...j], and that top operator is op[k].

Therefore every element/value v of E(i, j) can be written as either v = x + y, where x is an element of E(i, k), y is an element of E(k + 1, j) when op[k] = '+', or v = x - y where x is an element of E(i, k), y is an element of E(k + 1, j) when op[k] = '-'. Thus, the set of all possible values E(i,j) is the union of the results you can form by taking any possbile result from the left part [i, k] and combining it (with '+' or '-') with any possible result from the right. We want the max and min of that union

By the inductive hypothesis, the sets E(i, k) and E(k + 1, j) correctly represent their minimums and maximums. Consider two cases:
- Case 1: op[k] = '+'
For fixed k, the set {x + y : x ∈ E(i,k), y ∈ E(k+1,j)} has maximum maxVal[i][k] + maxVal[k + 1][j] and minimum minVal[i][k] + minVal[k + 1][j] because, in each argument, addition is monotone. Thus, the largest value obtainable using split k is maxVal[i][k] + maxVal[k+1][j] and the smallest is minVal[i][k] + minVal[k+1][j].
- Case 2: op[k] = '-'
For fixed k, the set {x − y : x ∈ E(i,k), y ∈ E(k+1,j)} has maximum maxVal[i][k] − minVal[k+1][j] and minimum minVal[i][k] − maxVal[k+1][j]. This continues to follow the monotonicity and the observation that x - y increases with x and decreases with y.

Combining over all k, the global maximum over E(i, j) is the maximum of the k-specific maxima and the minimum is the minimum of the k-specific minima. If op[k] = '+', candidateMax = maxVal[i][k] + maxVal[k + 1][j], candidateMin = minVal[i][k] + minVal[k + 1][j], and if op[k] = '-', candidateMax = maxVal[i][k] − minVal[k + 1][j], candidateMin = minVal[i][k] − maxVal [k + 1][j]. Taking the respective maximum/minimum of all candidateMax/candidateMin over k yields the true maximum/minimum for i, j. Thus, the DP correctly comptues maxVal[i][j] and minVal[i][j] for length l, completing the inductive step.

By induction, the algorithim is correctl for all intervals, in which maxVal[1][n] is the maximum value of the whole expression. QED.

## complexity:
The time complexity is the same as standard optimal parenthesization dynamic programming problem, O(n^3). This is because there are O(n^2) subproblems and each subproblem checks O(n) splits.