# Maximum expression by adding parentheses
### Problem
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 Description
The maximum value of a long expression, like $Exp(1, n)$, depends on the values of its sub-expressions. For example, if the last operation splits the expression at operator $o_k$, the expression becomes: $(v_1\ ... \ v_k) \ \ o_k \ \ (v_{k+1} \ \dots \ v_n)$

The value of this depends on the values of the two sub-expressions $Exp(1, k)$ and $Exp(k+1, n)$.
* To maximize an expression like A + B, A and B must be maximized.
* To maximize an expression like A - B, A must be maximized and B must be minimized.

Because of this, we must simultaneously compute both the max and min possible values for every sub-expression.

The algorithm will use two n x n DP tables:
* $max[i][j]$: The maximum possible value of the sub-expression from $v_i$ to $v_j$.
* $min[i][j]$: The minimum possible value of the sub-expression from $v_i$ to $v_j$.
* It will also separate the given array into an operator and a number array

fun findMax(A) {
    // calls on a function thats splits give sequence into numbers and operators
    var op, nums = split_into_num_and_op(A);
    var n = len(nums);
    
    // initialize both min and max 2d arrays size n x n
    var max = [][];    
    var min = [][];    
    
    
    // base case: smallest expression is a single number
    for (var i = 1; i < n; i++) {
        max[i][i] = num[i];
        min[i][i] = num[i];
    }
    
    for (var len = 2; len < n; len++) {
        // i = start index
        for (var i = 1; i < (n - len + 1); i++) {
            // j = end index
            var j = i + len - 1;
            
            max[i][j] = -99999;
            min[i][j] = 99999;
            
            for (var k = i; k < (j - 1); k++) {
                var operation = op[k];
                var maxVal, minVal;
                
                if (operation == '+') {
                    maxVal = max[i][k] + max[k+1][j];
                    minVal = min[i][k] + min[k+1][j];
                }
                else if (operation == '-') {
                    maxVal = max[i][k] - min[k+1][j];
                    minVal = min[i][k] - max[k+1][j];
                }    
            }
            max[i][j] = max(max[i][j], maxVal);
            min[i][j] = max(min[i][j], minVal);
        }
    }
    return max[1,n];
}

### Correctness Proof

#### Base Case

The smallest sub-expression is a single number (lenght = 1). Initialized the array diagonal as the numbers itself.
For any $i$ from 0 to $n$:
* $max[i][i] = num[i]$
* $min[i][i] = num[i]$

#### Recurrence Relation

We want to fill $max[i, j]$ and $min[i, j]$ for sub-expressions of increasing length. Let the length be $len$. We go through $len$ from 2 to $n$.

For any sub-expression from $i$ to $j$ (where $j = i + len - 1$), we try every possible split point $k$ (where $i \le k < j$). This $k$ represents $op[k]$ as the *last* operation performed, splitting the problem into sub-expressions $Exp(i, k)$ and $Exp(k+1, j)$.

We initialize $max[i][j] = -99999$ and $min[i][j] = \ 99999$. Then, for each $k$:

If $op[k]$ == '+':

* The max value is $max(E(i, k)) + \ max(E(k+1, j))$.
* $maxVal\ = max[i][k] + max[k+1][j]$
* The min value is $\min(E(i,\ k)) + \min(E(k+1,\ j))$.
* $minVal\ = min[i][k] + min[k+1][j]$

If $op[k]$ == '−':

* The max value is $max(E(i,\ k)) - \min(E(k+1,\ j))$.
* $maxVal= max[i,\ k] - max[k+1,\ j]$
* The min value is $min(E(i,\ k)) - \ max(E(k+1,\ j))$.
* $minVal = min[i][k] - max[k+1][j]$

We update $max[i, j]$ and $min[i, j]$ with the best values found:

* $max[i][j] = \max(max[i][j],\ maxVal)$
* $min[i][j] = \min(min[i][j],\ minVal)$

The final answer will be the maximum value for the entire expression, which is $max[1][n]$.

### Time Complexity
We have three nested loops.
* The outer loop for length $len$ runs $O(n)$ times.
* The second loop for start index $i$ runs $O(n)$ times.
* The inner loop for split point $k$ runs $O(n)$ times in the worst case.

This gives a total time complexity of $O(n \times n \times n) = O(n^3)$.