## Problem:


## Description
we r given an expression of integers separated by + and −, e.g.
1 + 3 − 2 − 5 + 1 − 6 + 7

We may add parentheses (only to group additions/subtractions; no implicit multiplication) to maximize the value. Design an efficient algorithm to compute that maximum value.
(This is exactly a matrix-chain-style DP: parenthesize a linear chain to optimize an objective.)

Because subtraction is not associative (and not monotone), for any subarray of numbers we must know both the minimum and the maximum value that subarray can produce.
When we split a subexpression nums[i…j] at position k, we combine the best/worst values on the left and right according to the operator between them.

---

## Recurrence

Let:

nums[0…n-1] be the numbers in order,

ops[0…n-2] be the operators between them ('+' or '-'),

Min[i][j] / Max[i][j] be the min/max value achievable from the sub-expression nums[i] ops[i] nums[i+1] … ops[j-1] nums[j].

Base:

Min[i][i] = Max[i][i] = nums[i]

Transition (for all i < j, for all i ≤ k < j):

If ops[k] == '+':

candidate_min = Min[i][k] + Min[k+1][j]
candidate_max = Max[i][k] + Max[k+1][j]

If ops[k] == '-':

candidate_min = Min[i][k] - Max[k+1][j] # smallest left minus largest right
candidate_max = Max[i][k] - Min[k+1][j] # largest left minus smallest right

Then

Min[i][j] = min over all splits k of candidate_min
Max[i][j] = max over all splits k of candidate_max

Answer: Max[0][n-1].

## Pseudocode

MaximizeExpression(nums[0..n-1], ops[0..n-2]):
    for i = 0..n-1:
        Min[i][i] = Max[i][i] = nums[i]

    for len = 2..n:                       # length of window
        for i = 0..n-len:
            j = i + len - 1
            Min[i][j] = +∞
            Max[i][j] = -∞
            for k = i..j-1:               # split at k (operator ops[k])
                if ops[k] == '+':
                    candMin = Min[i][k] + Min[k+1][j]
                    candMax = Max[i][k] + Max[k+1][j]
                else:  # '-'
                    candMin = Min[i][k] - Max[k+1][j]
                    candMax = Max[i][k] - Min[k+1][j]
                Min[i][j] = min(Min[i][j], candMin)
                Max[i][j] = max(Max[i][j], candMax)

    return Max[0][n-1]

## Correctness Proof

Induct on subexpression length L = j−i+1.

- Base L=1: Only one number, so Min=Max=that number—correct.
- Step: Assuming all windows shorter than L are correct. Any optimal parenthesization of nums[i…j] splits at some k.

- For '+', the min (max) of the whole must be the sum of mins (maxes) of the parts.
- For '−', the min is achieved by the smallest left minus the largest right; the max by the largest left minus the smallest right.
Our transitions enumerate all k and take the best feasible value, so we realize exactly the optimal value for i…j. QED.

---

## Time Complexity

- States: O(n^2) pairs (i,j).
For each state we try O(n) splits.

- Time O(n^3), space O(n^2).

(We can reconstruct an optimal parenthesization by storing which k achieved Max[i][j].)

## Example in hw

Expression: 1 + 3 − 2 − 5 + 1 − 6 + 7
Running the DP yields:
Maximum value = 21
Achieved by one valid parenthesization:
(1 + (3 - ((2 - (5 + 1)) - (6 + 7))))
Minimum value = −17 (e.g., (1+(((3-2)-(5+1))-(6+7))))

This solution follows the classic “parenthesize a chain” DP pattern (same structure as Matrix Chain Multiplication), extended to track min/max because subtraction is non-associative.