# Problem:
Given a list of integers seperated by + and - , place parentheses in different ways to get the maximum value.

# Solution:

algorithm descripition

# I want to find the maximum possible value by adding parentheses
# I’ll use dynamic programming similar to Matrix Chain Multiplication

def maxExpression(nums, ops):
    n = len(nums)
    
    # I’ll make two DP tables: one for max values and one for min values
    maxVal = [[0] * n for _ in range(n)]
    minVal = [[0] * n for _ in range(n)]
    
    # Base case: a single number by itself
    for i in range(n):
        maxVal[i][i] = nums[i]
        minVal[i][i] = nums[i]
    
    # Now I’ll expand the chain length from 2 up to n
    for L in range(2, n + 1):
        for i in range(n - L + 1):
            j = i + L - 1
            maxVal[i][j] = float('-inf')
            minVal[i][j] = float('inf')
            
            # I’ll try every split point k between i and j
            for k in range(i, j):
                op = ops[k]
                
                # compute all combinations for + or -
                if op == '+':
                    a = maxVal[i][k] + maxVal[k + 1][j]
                    b = minVal[i][k] + minVal[k + 1][j]
                else:  # op == '-'
                    a = maxVal[i][k] - minVal[k + 1][j]
                    b = minVal[i][k] - maxVal[k + 1][j]
                
                # I’ll store the best (max and min) outcomes
                maxVal[i][j] = max(maxVal[i][j], a, b)
                minVal[i][j] = min(minVal[i][j], a, b)
    
    # The final maximum value for the whole expression
    return maxVal[0][n - 1]

# correctness proof

I use optimal substructures such that:
* any of the lower expressions E[i..j] can be split at k where + or - is called.
* the maximum value E[i..j] depends on the values to the left and the right lower expressions
* Since + and - and associative, this recursive decomp. correctly covers all valid parentheses.

I also used overlapping subproblems
* lower expressions E[i..j] pop up multiple times in different recursive calls. The DP table stores and reuse results so it's only solved once (helps a TON with efficient)

Therefore this dymanmic programming approach ensures a efficient (maybe not optimal) solution.

# time complexity
**Time**
Each Subproblem (i,k) considers all split points k between them. since there are O(n^2) subproblems and each subproblem does O(n) splits...
The total sadly ends up being **O(n^3)**