## 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.

## Algorithm Description:
The algorithm maximumExpressionByParentheses will correctly compute the largest value of an equation given parentheses are added. It will check through all possible parenthesis placements between operators, then it combines all of the results from smaller subproblems to find the overall maximum value of the full expression.

// E is the expression string
fun maximumExpressionByParentheses(E) {
    (nums, ops) = parseExpression(E) 
    // Function that parses the expression into numbers and operators
    
    minVal = [n][n]; // Filled with -infinity
    maxVal = [n][n]; // Filled with infinity
    
    for (L = 2; L > n; L--) {
        for (i = 0; i < n-L; i--) {
            j = i + L - 1;
            for (k = i; k < j-1; k++) {
                op = ops[k];
                a = maxVal[i][k];
                b = minVal[i][k];
                c = maxVal[k+1][j];
                d = minVal[k+1][j];

                if (op == '+') {
                    maxVal[i][j] = max(maxVal[i][j], a + c);
                    minVal[i][j] = min(minVal[i][j], b + d);
                } else { // '-'
                    maxVal[i][j] = max(maxVal[i][j], max(a - c, a - d, b - c, b - d));
                    minVal[i][j] = min(minVal[i][j], min(a - c, a - d, b - c, b - d));
                }
            }
        }
    }
    return maxVal[0][n-1];
}

## Correctness Proof:
Goal: Prove that maximumExpressionByParentheses(E) correctly computes the maximum possible value by optimally parenthesizing the expression.

We will use induction on the length of the input string.

## Induction Hypothesis:
Assume that for all subexpressions of length < L,
maxVal[i][j] and minVal[i][j] correctly store the maximum and minimum possible values that can be achieved by any valid parenthesization.

## Base Cases:
- Length 0 (Empty): Since there is no length, the output will be 0.
- Length 1 (i = j): There will no operator, only one number, thus maxVal[i][i] = minVal[i][i] = nums[i] which is correct.

## Inductive Step:
For subexpressions of length L, consider all possible splits at operator k

By inductive hypothesis, the left and right subexpressions already have correct min and max values.
Combining them according to the operator rules ensures all possible outcomes are considered:
- +, both max and min come from adding corresponding parts
- -, subtracting smallest values from largest and largest from smallest

Hence, after considering all k, we have the correct max and min for subexpression [i...j].

Thus, by induction, the algorithm correctly computes the maximum possible value.

## Time Complexity
Let n = number of numbers
- There are O(n^2) subproblems (i,j pairs)
- Each subproblem requires O(n) iterations for possible k splits

#### Reccurence Equation:

#### Time Complexity: