# **Maximum Expression by Adding Parentheses**
Suppose you are given a sequence of integers separated by + and − signs; for

example:

1+3−2−5+1−6+7

You can change the value of this expression by adding parentheses in difference places. For example:

1+3−2−5+1−6+7 = −1 (1+3−(2−5))+(1−6)+7 = 9

(1+(3−2))−(5+1)−(6+7) = −17

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 as in 1 + 3(-2)(-5) + 1- 6 + 7 = 33.

[hint: you might find the matrix chain multiplication example in the slides inspiring for solving this]

# **Algorithm**
THe following algorithm uses the function ```maxExpression(E)``` to find the maximum value that an expression can produce by adding parentheses in any way. The algorithm first parses the expression into two arrays (using the helper function parseExpression(E)), nums (the values) and ops (the operators + or -). The algorithm then stores the max value of the subexpression from nums[i] to nums[j], while minVal[i][j] stores the minimum value of the subexpression. The results from the subexpressions will then be combined and the algorithm will find the max value of the entire expression.

fun maxExpression(E){
    (nums, ops) = parseExpression(E); //helper function for parsing, returns (nums, ops)
    var n = len(nums);
    
    var maxVal = [];
    var minVal = [];
    
    for(var i = 0; i < n; i = i++){
        var maxRow = [];
        var minRow = [];
        
        for(var i = 0; i < n; i = i++){
            if(i == j){
                push(maxRow, nums[i]);
                push(minRow, nums[i]);
            }
            else{
                push(maxRow, -999999);
                push(minRow, 999999);
            }
        }
        push(maxVal, maxRow);
        push(minVal, minRow);
        
    }
    
    for(var L = 2; L <= n; L++){
        for(var i = 0; i <= n - L; i++){
            var j = i + L - 1;
            
            for(var k = i; k < j; k++){
                var op = ops[k];
                var a = maxVal[i][k];
                var b = minVal[i][k];
                var c = maxVal[k + 1][j];
                var d = minVal[k + 1][j];
                
                if(op == '+'){
                    if(a + c > maxVal[i][j])
                        maxVal[i][j] = a + c;
                    if(b + d < minVal[i][j])
                        minVal[i][j] = b + d;
                }
                else{
                    var cand = [a - c, a - d, b - c, b - d];
                    for(var t = 0; t < len(cand); t++){
                        if(cand[t] > maxVal[i][j])
                            maxVal[i][j] = cand[t];
                        if(cand[t] < minVal[i][j])
                            minVal[i][j] = cand[t];
                    }
                }
            }
        }
    }
    

    return maxVal[0][n - 1];
}

# **Correctness Proof**
**Goal:** The function ```maxExpression(E)``` correctly finds and returns the maximum possible value of an expression E containing numbers and + or - symbols.

**Base Case:**
n = 0: if the subexpression is empty, the output will be 0.
n = 1: if the subexpression only contains one value --> maxVal[i][i] = minVal[i][i] = nums[i]

**Induction Hypothesis:**
Assume that for all subexpressions of length less than n, maxVal[i][j] and minVal[i][j] correctly store the max and min values for each subexpression.

Induction step --> n >= 2
1. Try every possible place k to split between i and j
2. maxVal[i][k], minVal[i][k], maxVal[k+1][j], and minVal[k+1][j] will store the values for the subexpressions
3. if the operator is '+' --> ```max = maxVal[i][k] + maxVal[k+1][j]``` and ```min = minVal[i][k] + minVal[k+1][j]```
4. if the operator is '-' --> candidates = [a - c, a - d, b - c, b - d]
5. a max and min is chosen from both

by induction, the algorithm correctly finds and returns the result for the expression.

QED.

# **Time Complexity**
Let n = # of values

for each subexpression:
* every point k is tried between i and j-1 --> O(n)
* there are O(n^2) subexpressions

T(n) = O(n^3)